9512.net

# Communicated by Bruce Rothschild

JOURNAL OF COMBINATORIAL THEORY, SERIES A ???, 1{21 ARTICLE NO. HA-00000

(???)

The Algebra and Combinatorics of Shu es and Multiple Zeta Values
Douglas Bowman
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, U.S.A. E-mail: bowman@math.uiuc.edu

Department of Mathematics and Statistics, University of Maine, Orono, Maine, U.S.A. E-mail: bradley@gauss.umemat.maine.edu; dbradley@e-math.ams.org Communicated by Bruce Rothschild

Received October 3, 2000; accepted April 11, 2001 The algebraic and combinatorial theory of shu es, 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. c ??? Academic Press
Key Words :

Lie algebra, shu e, multiple zeta value, iterated integral.

We continue our study of nested sums of the form (s1 ; s2 ; : : : ; sk ) :=
X

1. INTRODUCTION

k Y

n1 >n2 > >nk >0 j =1

? nj sj ;

(1)

commonly referred to as multiple zeta values 2, 3, 4, 11, 12, 16, 19]. Here and throughout, s1 ; s2 ; : : : ; sk are positive integers with s1 > 1 to ensure convergence.
1
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

2

D. BOWMAN & D. M. BRADLEY

There exist many intriguing results and conjectures concerning values of (1) at various arguments. For example, 2 4n (f3; 1gn) := (3; 1; 3; 1{z: : : ; 3; 1) = (4n + 2)! ; ; } |
2n

0 n 2 Z;

(2)

was conjectured by Zagier 19] and rst proved by Broadhurst et al 2] using analytic techniques. Subsequently, a purely combinatorial proof was given 3] based on the well-known shu e 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; 1gn. Given a non-negative integer n, let ~ = (m0 ; m1 ; : : : ; m2n ) be a vector of non-negative integers, and s consider the multiple zeta value obtained by inserting mj consecutive twos after the j th element of the string f3; 1gn for each j = 0; 1; 2; : : :; 2n:

Z (~) s

:= (f2gm ; 3; f2gm ; 1; f2gm ; 3; f2gm ; 1; : : : ; 3; f2gm n? ; 1; f2gm n ):
0 1 2 3 2 1 2

r For non-negative integers k and r, let Cr (k) denote the set of k+??1 orr 1 dered non-negative integer compositions of k having r parts. For example, C3 (2) = f(2; 0; 0); (0; 2; 0); (0; 0; 2); (0; 1; 1); (1; 0; 1); (1; 1; 0)g. Our generalization of (2) states (see Corollary 5.1 of Section 5) that
X

?

~2C2n+1 s

2 2m m Z (~) = (2m + 2)! 2n + 1 ; s +1 (m?2n)

(3)

for all non-negative integers m and n with m 2n. Equation (2) is the special case of (3) in which m = 2n, since Z (f0g2n+1) = (f3; 1gn). If again ~ = (m0 ; m1 ; : : : ; m2n ) and we put s
C(~) := Z (~) + s s
2n X

j =1

Z (mj ; mj+1 ; : : : ; m2n ; m0 ; : : : ; mj?1 );
2m m jC2n+1 (m ? 2n)j = (2m + 1)! 2n

then (see Theorem 5.1 of Section 5)
X

~2C2n+1 (m?2n) s

C(~) = Z (m) s

(4)

is an equivalent formulation of (3). The cyclic insertion conjecture 3] can be restated as the assertion that C(~) = Z (m) for all ~ 2 C2n+1 (m ? 2n) s s
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

3

and integers m 2n 0. Thus, our result reduces the problem to that of establishing the invariance of C(~) on C2n+1 (m ? 2n). s 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 multiple zeta values. In the nal section, we establish the aforementioned results (3) and (4). As Kontsevich 19] observed, (1) admits an iterated integral representation (s1 ; s2 ; : : : ; sk ) = of depth
Z Pk Z

2. ITERATED INTEGRALS
k 1Y

0 j =1

asj ?1 b

(5)

j =1 sj . Here, the notation j :=
Z

n xY

n Y

y j =1

x>t1 >t2 > >tn >y j =1

fj (tj ) dtj ;

j := fj (tj ) dtj

(6)

of 2] is used with a and b denoting the di erential 1-forms dt=t and dt=(1 ? t), respectively. Thus, for example, if f1 6= f2, we write 2 2 1 for 1 the integrand f1 (t1 )f1 (t2 )f2 (t3 )f1 (t4 ) dt1 dt2 dt3 dt4 : Furthermore, we shall agree that any iterated integral of an empty product of di erential 1-forms is equal to 1. This convention is mainly a notational convenience; nevertheless we shall nd it useful for stating results about iterated integrals more concisely and naturally than would be possible otherwise. Thus (6) reduces to 1 when n = 0 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 ? possible interlacings of the variall ables. Thus if we denote the set of all n+m permutations of the indices n f1; 2; : : :; n + mg satisfying ?1 (j ) < ?1 (k) for all 1 j < k n and n + 1 j < k n + m by Shu (n; m), then we have the self-evident formula
Z

n xY

Z

y j =1

j

+m x nY

y j =n+1

j =

X

Z

+m x nY

2Shu (n;m) y j=1

(j ) ;

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

4
n Y j =1

D. BOWMAN & D. M. BRADLEY

and so de ne the shu e product
j nY +m j =n+1

by
j :=
X

nY +m

2Shu (n;m) j=1

(j ) :

(7)

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 1 2 n and n+1 n+2 n+m are preserved. The term \shu e" is used because such permutations arise in ri e shu ing a deck of n + m cards cut into one pile of n cards and a second pile of m cards. The study of shu es 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 di erential 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 1 ; 2 ; : : : ; n be di erential 1forms and let x; y 2 R. Then
Z

x

y

1 2

n = (?1)n

Z

y

x

n n?1

1:

Proof. Suppose j = fj (tj ) dtj . Observe that
Z

x

y

f1 (t1 )
=
Z

Z

t1

x

y

f2 (t2 )
Z

Z tn?1

y

fn (tn )

x

y

fn(tn ) dtn dtn?1
Z

dt1 dtn :

tn

fn?1 (tn?1 )

x

t2

f1 (t1 ) dt1 dt2

Now switch the limits of integration at each level. Proposition 2.2 ( 6, Lemma 1.1]). Let 1 ; 2 ; : : : ; n be di erential 1-forms and let y z x. Then
Z

n xY

y j =1

j=

n X k=0

Z

k xY z j =1

Z

j

z

n Y

y j =k+1

j

:

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

5

Proof.

(t1 ; t2 ; : : : ; tn ) 2 Rn : x > t1 > t2 > =
n k=0

> tn > y > tk > z > tn > y :

(t1 ; : : : ; tk ) 2 Rk : x > t1 >

(tk+1 ; : : : ; tn ) 2 Rn?k : z > tk+1 >

A related version of Proposition 2.2, \Holder 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. We have seen how shu es arise in the study of iterated integral representations for multiple zeta values. Following 15] (cf. also 3, 18]) let A be a nite 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 nite 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 shu e product is alternatively de ned rst on words by the recursion 1 w = w 1 = w; (8) au bv = a(u bv) + b(au v); and then extended linearly to QhAi. One checks that the shu e product so de ned is associative and commutative, and thus QhAi equipped with the shu e 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 de nition (8) has its analytical motivation in the formula for integration by parts|equivalently, the product rule for di erentiation. Thus, if we put a = f (t) dt, b = g(t) dt and
(

3. THE SHUFFLE ALGEBRA

8w 2 A ; 8a; b 2 A; 8u; v 2 A ;

F (x) :=

Z

x

y

(au

bv) =

Z

x

y

f (t)

Z

t

y

u dt

Z

x y

g(t)

Z

t y

v dt ;
???

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

6

D. BOWMAN & D. M. BRADLEY

R then writing F (x) = yx F 0 (s) ds and applying the product rule for di erentiation yields

F (x) =

Z

x

y
Z

f (s)

Z

s

+ =
x y

Z

y

u
x

Z

s

y

g(t)
s y

Z

t

y

g(s)

Z

y

v dt ds
t y

f (t) v)] :

Z

u dt

Z

s

y

v ds

a(u

bv) + b(au

Alternatively, by viewing F as a function of y, we see that the recursion could equally well have been stated as
(

8w 2 A ; 8a; b 2 A; 8u; v 2 A ;

ua

1

w = w 1 = w; vb = (u vb)a + (ua

v)b:

(9)

Of course, both de nitions are equivalent to (7).

The following relatively straightforward results concerning Q-algebra homomorphisms on shu e 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 de nition explicit. Definition 3.1. Let R and S be rings with identity, and let A and B be alphabets. A ring anti-homomorphism : RhAi ! S hB i is an additive, R-linear, identity-preserving map that satis es (u) (v) = (vu) for all u; v 2 A (and hence for all u; v 2 RhAi).
Proposition 3.1. Let A and B be alphabets. A ring anti-homomorphism : QhAi ! QhB i induces a Q-algebra homomorphism of shu e algebras : ShQ A] ! ShQ B ] in the natural way.

3.1. Q-Algebra Homomorphisms on Shu e Algebras

Proof. It su ces to show that (u v) = (u) (v) for all u; v 2 A . The proof is by induction, and will require both recursive de nitions of the shu e product. Let u; v 2 A be words. For the base case, note (u) and likewise with the empty word on that (1 u) = (u) = 1 the right. For the inductive step, let a; b 2 A be letters and assume that (bv) and (au v) = (au) (v) both hold. (u bv) = (u)
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

7

Then as is an anti-homomorphism of rings, (au bv) = (a(u bv) + b(au v)) = (a(u bv)) + (b(au v)) = (u bv) (a) + (au v) (b) (bv)] (a) + (au) (v)] (b) = (u) = (u) (v) (b)] (a) + (u) (a) (v)] (b) (v) (b) = (u) (a) = (au) (bv): Of course, there is an analogous result for ring homomorphisms. Proposition 3.2. Let A and B be alphabets. A ring homomorphism : QhAi ! QhB i induces a Q-algebra homomorphism of shu e algebras : 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 de nitions of the shu e product. Alternatively, one can put u = a1 a2 an , v = an+1 an+2 an+m and verify the equation (u v) = (u) (v) using (7) and the hypothesis that 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 Q Q all a 2 A. Then R( n=1 aj ) = n=1 an?j+1 for all a1 ; : : : ; an 2 A, so that j j R is a string-reversing involution which induces a shu e algebra automorphism of ShQ A]. We shall reserve the notation R for this automorphism throughout. Example 2. Let A = fa; bg and let S : QhAi ! QhAi be the ring automorphism induced by the assignments S (a) = b, S (b) = a: Then the composition := S R is a letter-switching, string-reversing involution which induces a shu e algebra automorphism of ShQ A]. In the case a = dt=t, b = dt=(1 ? t), this is the so-called Kontsevich duality 19, 1, 2, 16] for iterated integrals obtained by making the change of variable t 7! 1 ? 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 2k .
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

8

D. BOWMAN & D. M. BRADLEY

Example 3. Let A = fa; bg; B = fb; cg and let : QhAi ! QhB i be the letter-shifting, string-reversing ring anti-homomorphism induced by the assignments (a) = b and (b) = c. Then induces a shu e algebra isomorphism : ShQ A] ! ShQ B ]. With the choice of di erential 1forms a = dt=t, b = dt=(1 ? t), c = ?dt=(1 + t), maps shu e identities 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 su ces to assert that they are important instances|as are multiple zeta values|of multiple polylogarithms 2, 10].

Let A be an alphabet, and let X = fXa : a 2 Ag be a set of card(A) distinct non-commuting indeterminates. Every element in QhX i can be written as a sum F = F0 + F1 + where Fn 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 F0 = 0 are referred to as Lie elements. Let X : QhAi ! QhX i be the canonical ring isomorphism induced by the assignments X(a) = Xa for all a 2 A. If Y = fYa : a 2 Ag is another set of non-commuting indeterminates, we similarly de ne Y : QhAi ! QhY i to be the canonical ring isomorphism induced by the assignments Y(a) = Ya for all a 2 A. Let us suppose X = X(A) and Y = Y(A) are disjoint and their elements commute with each other, so that for all a; b 2 A we have Xa Yb = Yb Xa . If we de ne addition and multiplication in Q X; Y] by (X + Y)(a) = Xa + Ya and (XY)(a) = Xa Ya for all a 2 A, then Q X; Y] becomes a commutative Q-algebra of ring isomorphisms Z. For example, if Z = X + Y and w = a1 a2 an where a1 ; a2 : : : ; an 2 A, then

3.2. A Lie Exponential

Z(w) = (X + Y)(a1 a2 an) =
G(Z) :=
Evidently,

n Y

Let G : Q X; Y] ! (ShQ A])hhX; Y ii be de ned by
X

j =1

(X + Y)(aj ) =

n Y?

j =1

Xaj + Yaj :
(10)

w2A

wZ(w):
n

G(X) = 1 +

1 X

X

More importantly, G is a homomorphism from the underlying Q-vector space to the underlying multiplicative monoid ((ShQ A])hhX; Y ii; ):
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

n=1 a2A

aXa

= 1 ? P 1 aX : a2A a

(11)

???

SHUFFLES AND MULTIPLE ZETA VALUES

9

Theorem 3.1. The map G : Q X; Y] ! (ShQ A])hhX; Y ii de ned by (10) has the property that

G(X + Y) = G(X)
Proof. On the one hand, we have

G(Y):

G(X + Y) =
whereas on the other hand,

X

w2A

w(X + Y)(w);

G(X)

G(Y) =

X

u2A

uX(u)

X

v2A

vY(v) =

X

u;v2A

(u

v)X(u)Y(v):

Therefore, we need to show that
X

u;v2A

(u

v)X(u)Y(v) =

X

w2A

w(X + Y)(w):

But,
X

u;v2A

(u
X

v)X(u)Y(v)
n X k Y

=

Yaj j =1 j =k+1 n k Y Y Yaj ; = a (r) Xaj j =1 n 0 a1 ;:::;an 2A k=0 2Shu (k;n?k) r=1 j =k+1
n 0 a1 ;:::;an 2A k=0 j =1 n X X X X j =k+1 n Y

X

aj

n Y

aj

k Y

Xaj

n Y

using the non-recursive de nition (7) of the shu e product. For each 2 Shu (k; n ? k), if a1 ; : : : ; an run through the elements of A, then so do
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

10

D. BOWMAN & D. M. BRADLEY
(1) ; : : : ; a (n) .
X

a

Hence putting bj = a (j) , we have that

u;v2A

(u
X

v)X(u)Y(v)
n Y r=1 n Y k=0 2Shu (k;n?k) j =1 n Y (Xbj + Ybj ) br r=1 j =1

= = =

X

n 0 b1 ;:::;bn 2A
X X X

br

n X

X

k Y

Xb ?

n Y j =k+1

1 (j )

Yb ?

1 (j )

n 0 b1 ;:::;bn 2A w2A

w(X + Y)(w):

In the penultimate step, we have summed over all n shu es of the ink determinates X with the indeterminates Y; yielding all 2n possible choices obtained by selecting an X or a Y from each factor in the product (Xb + Yb ) (Xbn + Ybn ).
1 1

?

Remarks. Theorem 3.1 suggests that the map G de ned 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

G(X) = 1 +

1 X aX a n=1 n! a2A

1 X

n

:

Just as the functional equation for the exponential function is equivalent to the binomial theorem, Theorem 3.1 is equivalent to the following shu e analog of the binomial theorem:
Proposition 3.3 (Binomial Theorem in QhX ihY i). Let X = fX1 ; X2 ; : : : ; Xn g and Y = fY1 ; Y2 ; : : : ; Yn g be disjoint sets of non-commuting indeterminates such that Xj Yk = Yk Xj for all 1 j; k n. Then n Y j =1

(Xj + Yj ) =

n X

X

k Y

k=0 2Shu (k;n?k) j =1

X

?1 (j )

n Y j =k+1

Y

?1 (j ) :

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

11

Chen 6, 7] considered what is in our notation the iterated integral of (10), namely

Gx := y

X Z

x

w2A y

wX(w)

(12)

in which the alphabet A is viewed as a set of di erential 1-forms. He proved 6, Theorem 6.1], 7, Theorem 2.1] the non-commutative generating function formulation

Gx = Gx Gz ; y z y

y z x

of Proposition 2.2 and also proved 7, Theorem 4.2] that if the 1-forms are piecewise continuously di erentiable, then log Gx is a Lie element, or y equivalently, that Gx is a Lie exponential. However, Ree 18] showed that y a formal power series log 1 +
X X

n>0 1 j1 ;:::;jn m

c(j1 ; : : : ; jn )Xj

1

Xjn

in non-commuting indeterminates Xj is a Lie element if and only if the coe cients satisfy the shu e relations

c(j1 ; : : : ; jn )c(jn+1 ; : : : ; jn+k ) =

X

2Shu (n;k)

c(j

(1) ; : : : ; j (n+k) );

for all non-negative integers n and k. Using integration by parts, Ree 18] showed that Chen's coe cients do indeed satisfy these relations, and that more generally, G(X) as de ned 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 shu e operation. The result is restated below in our notation. Theorem 3.2 ( 18, Theorem 2.6]). Let A be an alphabet, let X = fXa : a 2 Ag be a set of non-commuting indeterminates and let X : QhAi ! QhX i be the canonical ring isomorphism induced by the assignments X(a) = Xa for all a 2 A. Let G(X) be as in (11), let R be as in Example 1, and put

H (X) :=

X

w2A

(?1)jwjR(w)X(w);
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

12

D. BOWMAN & D. M. BRADLEY

where jwj denotes the length of the word w. Then G(X) H (X) = 1. It is convenient to state the essential ingredient in our proof of Theorem 3.2 as an independent result.

w 2 A , we have

Lemma 3.1. Let A be an alphabet and let R be as in Example 1. For all
X

u;v2A uv=w

(?1)juj R(u)

v = jwj;0:

(13)

Remarks.

We have used the Kronecker delta
(

n;k :=

1 if n = k; 0 otherwise.

Since R is a Q-algebra automorphism of ShQ A], applying R to both sides of (13) yields the related identity
X

u;v2A uv=w

(?1)juj u

R(v) = jwj;0;

w2A :

Proof of Lemma 3.1. First note that if we view the elements of A as di erential 1-forms and integrate the left hand side of (13) from y to x, then we obtain
X

u;v2A uv=w

(?1)juj

Z

x

y

R(u)

Z

x

y

v=

X Z

y

u;v2A x uv=w

u

Z

x

y

v=

Z

y y

w = jwj;0

by Propositions 2.1 and 2.2. For an integral-free proof, Q proceed as we follows. Clearly (13) holds when jwj = 0, so assume w = n=1 aj where j a1 ; : : : ; an 2 A and n is a positive integer. Let Sn denote the group of permutations of the set of indices f1; 2; : : :; ng, and let the additive weightfunction W : 2Sn ! A map subsets of Sn to words as follows:

W (S ) :=
???

n XY

2S j=1

a (j) ;

S Sn :

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

SHUFFLES AND MULTIPLE ZETA VALUES

13

For k = 0; 1; : : :; n let

ck := W (f 2 Sn : ?1 (i) < ?1 (j ) for k i > j 1 and k + 1 i < j ng); bk := W (f 2 Sn : ?1 (i) < ?1 (j ) for k i > j 1 and k i < j ng):
Then c0 = b1 , cn = bn and ck = bk + bk+1 for 1 k n ? 1. Thus,
X

u;v2A uv=w

(?1)juj R(u)

v =
=

n X

k=0 n X k=0

(?1)k

k Y j =1

ak?j+1

n Y j =k+1

aj

(?1)k ck

= 0; since the sums telescope.

n?1 n bn + X (?1)k (bk + bk+1 ) = b1 + (?1) k=1 n?1 n X X = b1 + (?1)n bn + (?1)k bk ? (?1)k bk k=1 k=2

Remark. One can also give an integral-free proof of Lemma 3.1 by induction using the recursive de nition (9) of the shu e product. Proof of Theorem 3.2. By Lemma 3.1, we have
X

= =

u2A

(?1)jujR(u)X(u)
u;v2A uv=w X(w) jwj;0

X

X

w2A w2A

X(w)

X

(?1)jujR(u)

v2A

vX(v) v

X

= 1:

Since (ShQ A])hhX ii is commutative with respect to the shu e product, the result follows.
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

14

D. BOWMAN & D. M. BRADLEY

The combinatorial proof 3] of Zagier's conjecture (2) hinged on expressing the sum of the words comprising the shu e product of (ab)p with (ab)q as a linear combination of basis subsums Tp+q;n . To gain a deeper understanding of the combinatorics of shu es on two letters, it is necessary to introduce additional basis subsums. We do so here, and thereby nd 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 de nitions of the basis subsums follow. Definition 4.1. ( 3]) For integers m n 0 let Sm;n denote the set of words occurring in the shu e product (ab)n (ab)m?n in which?the m subword a2 appears exactly n times, and let Tm;n be the sum of the 2n distinct words in Sm;n : For all other integer pairs (m; n) it is convenient to de ne Tm;n := 0.
Definition 4.2. For integers m n + 1 2, let Um;n be the sum of the elements of the set of words arising in the shu e product of b(ab)n?1 with b(ab)m?n?1 in which the subword b2 occurs exactly n times. For all other integer pairs (m; n) de ne Um;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,

4. COMBINATORICS OF SHUFFLE PRODUCTS

(ab)p

(ab)q =

min(p;q) X

n=0

4n p + q ? 2n Tp+q;n : p?n

(14)

The corresponding result for our basis (De nition 4.2) is Proposition 4.2. For all positive integers p and q ,

b(ab)p?1

b(ab)q?1 = 1

n p + q ? 2n Up+q;n : 2 n=1 4 p?n

min(p;q) X

(15)

Proof of Proposition 4.2. See the proof of Proposition 4.1 given in 3]. The only di erence here is that a2 occurs one less time per word than b2 and so the multiplicity of each word must be divided by 2. The index of
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

15

summation now starts at 1 because there must be at least one occurrence of b2 in each term of the expansion.
Corollary 4.1. For integers

p 1 and q 0,

b(ab)p?1

(ab)q =

min(p?1;q) X

4n p + q ? 2n a Up+q;n : +1 2 n=1 p?n
Proof. From (8) it is immediate that

n=0 min(p;q) X

? 4n p + q ? 2n 1 1 b Tp+q?1;n p?n?

(16)

b(ab)p?1

(ab)q = b (ab)p?1

(ab)q ] + a b(ab)p?1

b(ab)q?1 ]:

Now apply (14) and Proposition 4.2.
Proposition 4.3. Let x0 ; x1 ; : : : and y0 ; y1 ; : : : be sequences of not necessarily commuting indeterminates, and let m be a non-negative (respectively, positive) integer. We have the shu e convolution formul m X k=0

xk ym?k (ab)k
=

(ab)m?k
bm=2c X
n=0

4n

m?2n X j =0

m ? 2n x y n+j m?n?j Tm;n ; (17) j

and
m?1 X k=1

xk ym?k b(ab)k?1

b(ab)m?k?1

X X 1 bm=2c 4n m?2n m ? 2n x y =2 n+j m?n?j Um;n ; (18) j n=1 j =0

respectively.
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

16

D. BOWMAN & D. M. BRADLEY

Proof. Starting with the left hand side of (17) and applying (14), we nd that
m X k=0 m X

xk ym?k (ab)k xk ym?k
4n 4n
n=0

(ab)m?k 4n m ? 2n Tm;n k?n

= = =

min(X ?k) k;m

k=0 bm=2c X n=0

m?n X

bm=2c X
n=0

m?2n X j =0

xk ym?k m ? 2n Tm;n k?n k=n

m ? 2n x y n+j m?n?j Tm;n ; j

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 formul to hold. Thus, there are many possible special cases that can be examined. Here we will consider only one major application. If we con ne 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 shu e convolution formul
m X k=0 m?1 X k=1

xk ym?k (ab)k

(ab)m?k =

bm=2c X
n=0

(4xy)n (x + y)m?2n Tm;n

(19)

for all non-negative integers m, and

xk ym?k b(ab)k?1

b(ab)m?k?1 = 1

n m?2n Um;n 2 n=1 (4xy) (x + y) (20)

bm=2c X

for all integers m 2. Proof. In Proposition 4.3, put xk = xk and yk = yk for each k apply the binomial theorem.

0 and

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES

17

In this nal section, we establish the results (3) and (4) stated in the introduction. Let Sm;n be as in De nition 4.1. Each word in Sm;n has a unique representation (ab)m0
n Y k=1

5. CYCLIC SUMS IN ShQ A; B]

(a2 b)(ab)m k? b(ab)m k ;
2 1 2

(21)

in which m0 ; m1 ; : : : ; m2n are non-negative integers with sum m0 + m1 + + m2n = m ? 2n. Conversely, every ordered (2n + 1)-tuple (m0 ; m1 ; : : : ; m2n ) of non-negative integers with sum m ? 2n gives rise to a unique word in Sm;n via (21). Thus, a bijective correspondence ' is established between the set Sm;n and the set C2n+1 (m ? 2n) of ordered non-negative integer compositions of m ? 2n with 2n + 1 parts. In view of the relationship (5) expressing multiple zeta values as iterated integrals, it therefore makes sense to de ne

Z (~) := s

Z

1

0

'(~); s
Z

~ 2 C2n+1 (m ? 2n); s
n Y k=1

a := dt=t; b := dt=(1 ? t):

Thus, if ~ = (m0 ; m1 ; : : : ; m2n ), then s

Z (~) = s

1

= (f2gm ; 3; f2gm ; 1; f2gm ; 3; f2gm ; 1; : : : ; 3; f2gm n? ; 1; f2gm n );
0 1 2 3 2 1 2

0

(ab)m

0

(a2 b)(ab)m k? b(ab)m k
2 1 2

in which the argument string consisting of mj consecutive twos is inserted after the j th element of the string f3; 1gn for each j = 0; 1; 2; : : :; 2n. From 1] we recall the evaluation

f0; 1; 2; : : :; 2ng. For 2 S2n+1 we de ne a group action on C2n+1 (m ? 2n)
by ~ = (m s Let
?1 (0) ; m ?1 (1) ; : : : ; m ?1 (2n) ),

Let

S2n+1 denote the group of permutations on the set of indices
2n X

Z (m) = (f2gm ) = (2m + 1)! ;

2m

0 m 2 Z:

(22)

where ~ = (m0 ; m1 ; : : : ; m2n ). s

C(~) := s

j =0

Z ( j ~); s

= (0 1 2 : : : 2n)

(23)

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 ??? by Academic Press All rights of reproduction in any form reserved.

???

18

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 speci cally, it is conjectured that Conjecture 5.1. For any non-negative integers m0 ; m1 ; : : : ; m2n , we have
C(m0 ; m1 ; : : : ; m2n ) = Z (m) =
P n where m := 2n + 2=0 mj . j

(2m + 1)! ;

2m

An equivalent generating function formulation of Conjecture 5.1 follows. Conjecture 5.2. Let x0 ; x1 ; : : : be a sequence of commuting indeterminates. Then
2n 2n X C(m ; m ; : : : ; m ) y 0 1 2n j =0 n=0 mj 0 0 j 2n bm=2c 1 X X = Z (m) y2n (x0 + x1 + m=0 n=0

1 X

x mj j
+ x2n )m?2n :

To see the equivalence of Conjectures 5.1 and 5.2, observe that by the multinomial theorem,
1 X
m=0

Z (m)

bm=2c X
n=0

y2n(x0 + x1 +

+ x2n )m?2n + x2n )m?2n

= = =

1 X

n=0

y2n y2n y2n

X

1 X

m 2n
X

Z (m)(x0 + x1 + Z (m) Z (m)
X
2

n=0

1 X

m 2n
X

m0 +

2n m0 + + m2n Y xmj j +m n =m?2n m0 ; : : : ; m2n j =0
X

2n

n=0

m 2n

m0 + +m2n =m?2n j =0

x mj : j

Now compare coe cients. Although Conjecture 5.1 remains unproved, it is nevertheless possible to reduce the problem to that of establishing the invariance of C(~) for ~ 2 C2n+1 (m ? 2n). More speci cally, we have the s s following non-trivial result.
Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

SHUFFLES AND MULTIPLE ZETA VALUES
Theorem 5.1. For all non-negative integers m and

19

n with m 2n, X m C(~) = Z (m) jC2n+1 (m ? 2n)j = Z (m) s 2n : ~2C n (m?2n) s
2 +1

Example 4.

If m = 2n, Theorem 5.1 states that
C(f0g2n+1 ) = (2n + 1) (f3; 1gn ) = Z (2n);

which is equivalent to the Broadhurst-Zagier formula (2) (Theorem 1 of 3]).
Example 5.

If m = 2n + 1, Theorem 5.1 states that (2n + 1)C(1; f0g2n) = (2n + 1)Z (2n + 1);

which is Theorem 2 of 3]. For m > 2n + 1, 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 Tm;n be as in Definition 4.1, and put a = dt=t, b = dt=(1 ? t). Then, for all non-negative integers m and n, with m 2n,
X

~2C2n+1 (m?2n) s

Z (~) = s

Z

1 0

2 2m m Zm m Tm;n = 2n(+ )1 2n = (2m + 2)! 2n + 1 : +1

(24)

Proof of Theorem 5.1. In view of the equivalent reformulation (24) and the well-known evaluation (22) for Z (m), it su ces to prove that with Tm;n as in De nition 4.1 and with a = dt=t, b = dt=(1 ? t), we have
Z

1

0

2 2m m Tm;n = (2m + 2)! 2n + 1 : +1

Let

J (z ) :=

1 X
k=0

z 2k

Z

1

0

(ab)k =

1 X
k=0

z 2k (f2gk ):
???

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

20

D. BOWMAN & D. M. BRADLEY

Then 1] J (z ) = (sinh( z ))=( z ) for z 6= 0 and J (0) = 1. We have z sin z cos J (z cos )J (z sin ) = sinh(z cos ) sinh(z sin ) ? = cosh z (cos +2sinz 2)sin cosh z (cos ? sin ) 2 cos p p cosh z 1 + sin 2 ? cosh z 1 ? sin 2 = 2 z 2 sin 2 1 ( z )2m f(1 + sin 2 )m ? (1 ? sin 2 )m g X = (2m)! 2 z 2 sin 2 =
X 2( z )2m bm=2c m + 1 (sin 2 )2n : m=0 (2m + 2)! n=0 2n + 1

m=1

1 X

(25)

On the other hand, putting x = z 2 cos2 and y = z 2 sin2 in Theorem 4.1 yields

J (z cos )J (z sin )
= = = =
1 X 1 m XX
k=0

(z cos

)2k

Z

1

0

(ab)k

1 X
j =0

(z sin
Z

)2j

Z

1

0

(ab)j

m=0 n=0 1 X X bm=2c m=0 n=0

(z cos )2n (z sin )2m?2n

1 0

(ab)n

(ab)m?n
Z

(4z 4 sin2 cos2 )n (z 2 cos2 + z 2 sin2 )m?2n (sin 2 )2n
Z

1 0

Tm;n
(26)

1 X

m=0

z 2m

bm=2c X
n=0

1

0

Tm;n:

Equating coe cients of z 2m (sin 2 )2n in (25) and (26) completes the proof.

Thanks are due to the referee whose comments helped improve the exposition. 1. Jonathan M. Borwein, David M. Bradley and David J. Broadhurst, \Evaluations of k-fold Euler/Zagier Sums: A Compendium of Results for Arbitrary k," Elec. J. Comb., 4 (1997), No. 2, #R5. ???

ACKNOWLEDGMENT REFERENCES

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

SHUFFLES AND MULTIPLE ZETA VALUES

21

2. Jonathan M. Borwein, David M. Bradley, David J. Broadhurst and Petr Lisonek, \Special Values of Multiple Polylogarithms," Trans. Amer. Math. Soc. (to appear). 3. Jonathan M. Borwein, David M. Bradley, David J. Broadhurst and Petr Lisonek, \Combinatorial Aspects of Multiple Zeta Values," Elec. J. Comb., 5 (1998), No. 1, #R38. 4. Doug Bowman and David M. Bradley, \Resolution of Some Open Problems Concerning Multiple Zeta Evaluations of Arbitrary Depth," submitted October, 1999. 5. David J. Broadhurst, private e-mail, 1997. 6. Kuo-Tsai Chen, \Iterated Integrals and Exponential Homomorphisms," Proc. London Math. Soc., (3) 4 (1954), 502{512. 7. Kuo-Tsai Chen, \Integration of Paths, Geometric Invariants and a Generalized Baker-Hausdor Formula," Ann. of Math., 65 (1957), No. 1, 163{178. 8. Kuo-Tsai Chen, \Algebras of Iterated Path Integrals and Fundamental Groups," Trans. Amer. Math. Soc., 156 (1971), 359{379. 9. K. O. Friedrichs, \Mathematical Aspects of the Quantum Theory of Fields, V," Comm. Pure Appl. Math., 6 (1953), 1{72. 10. Alexander B. Goncharov, \Multiple Polylogarithms, Cyclotomy and Modular Complexes," Math. Res. Lett., 5 (1998), No. 4, 497{516. 11. Michael E. Ho man, \Algebraic Structures on the Set of Multiple Zeta Values," preprint. 12. Michael E. Ho man and Yasuo Ohno, \Relations of Multiple Zeta Values and their Algebraic Expression," preprint. 13. R. C. Lyndon, \A Theorem of Friedrichs," Mich. Math. J., 3 (1955-1956), 27{29. 14. Wilhelm Magnus, \On the Exponential Solution of Di erential Equations for a Linear Operation," Comm. Pure Appl. Math., 7 (1954), 649{673. 15. Hoang Ngoc Minh and Michel Petitot, \Lyndon words, polylogarithms and the Riemann function," Discrete Mathematics, 217(1-3) (2000), 273{292. 16. Yasuo Ohno, \A Generalization of the Duality and Sum Formulas on the Multiple Zeta Values," J. Number Theory, 74 (1999), 39{43. 17. David E. Radford, \A Natural Ring Basis for the Shu e Algebra and an Application to Group Schemes," J. Algebra, 58 (1979), 432{454. 18. Rimhak Ree, \Lie Elements and an Algebra Associated with Shu es," Ann. of Math., 62 (1958), No. 2, 210{220. 19. Don Zagier, \Values of Zeta Functions and their Applications," First European Congress of Mathematics, Vol. II, Birkhauser, Boston, 1994, pp. 497{512.

Copyright c ??? by Academic Press All rights of reproduction in any form reserved.

???

2013江苏高考英语完型与阅读真题解析
Bruce Rothschild of the University of Kansas knewall this when he began a study of ichthyosaur bones to find out how widespread the problem was in the...

Bruce Rothschild 说:"那可真够刺激。当他正与别人合作时,趁着 他还没回到你身边,你还有点时间考虑考虑。你还有机会知道别人正 7 在着手解决什么问题。"厄多斯...

Bruce Rothschild of the University of Kansas knewall this when he began a study of ichthyosaur bones to find out how widespread the problem was in ...

C If a diver surfaces too quickly, he may suffer th...
Bruce Rothschild of the University of Kansas knewall this when he began a study of ichthyosaur bones to find out how widespread the problem was in the...

Bruce Rothschild of the University of Kansas knew all this when he began a study of ichthyosaur bones to find out how widespread the problem was in ...

Bruce Rothschild of the University of Kansas knew all this when he began a study of ichthyosaur bones to find out how widespread the problem was in ...

Bruce Rothschild of the University of Kansas knew all this when he began a study of ichthyosaur bones to find out how widespread the problem was in ...
CIf a diver surfaces too quickly, he may suffer the...
Bruce Rothschild of the University of Kansas knewall this when he began a study of ichthyosaur bones to find out how widespread the problem was in the...

Bruce Rothschild of the University of Kansas knewall this when he began a study of ichthyosaur bones to find out how widespread the problem was in the...