Euler Sums and Contour Integral Represen

Euler Sums and Contour Integral Representations Philippe Flajolet and Bruno Salvy CONTENTS 1. Introduction 2. General summations 3. Linear Euler sums 4. Quadratic Euler sums 5. Cubic and higher order Euler sums 6. Models of Euler sum identities 7. Alternating Euler sums 8. Exotic sums Acknowledgements ReferencesW ork supp orted in part b y the Long T erm Researc h Pro jectA lc om/-IT /(/# /2/0/2/4/4/) of the Europ ean Union/.This paper develops an approach to the evaluation of Euler sums that involve harmonic numbers, either linearly or non- linearly. We give explicit formulæ for several classes of Eu ler sums in terms of Riemann zeta values. The approach is based on simple contour integral representations and residue com - putations. 1. INTRODUCTIONHarmonic n um b ers and their generalizations areclassically de/ned b yHn / H /(/1/)n /:/= nXj /=/1 /1j /; H /( r /)n /:/= nXj /=/1 /1j r /:The sub ject of this pap er is Euler sums /, whic h arethe in/nite sums whose general term is a pro duct ofharmonic n um b ers of index n and a p o w er of n /BnZr /1/.It has b een disco v ered in the course of the y earsthat man y Euler sums admit expressions in v olving/nitely the /\zeta v alues/"/, that is to sa y v alues ofthe Riemann zeta function/,/ /( s /) /:/= /1Xj /=/1 /1j sat the p ositiv e in tegers/. T ypical ev aluations to b ediscussed here are sho wn at the top of the nextpage/.Euler started this line of in v estigation in thecourse of a corresp ondence with Goldbac h b egin/-ning in /1/7/4/2 /(see /[Berndt /1/9/8/9/, p/. /2/5/3/] for a dis/-cussion/) and he w as the /rst to consider the line arsums/,Sp/;q /:/= /1Xn /=/1 H /( p /)nn q /: (1–1) c/ A K Peters, Ltd. 1058-6458/1998 $0.50 per page Experimental Mathematics 7:1, page 15 16 Experimental Mathematics, Vol. 7 (1998), No. 1/(a/) Xn / /1 Hnn /2 /= /2 / /(/3/) /; Xn / /1 Hnn /3 /= /5/4 / /(/4/) /; Xn / /1 Hnn /4 /= /3 / /(/5/) /BnZr / /(/2/) / /(/3/)/(b/) Xn / /1 H /(/2/)nn /4 /= / /(/3/) /2/BnZr /1/3 / /(/6/)/(c/) Xn / /1 H /(/2/)nn /5 /= /5 / /(/2/) / /(/5/) /+ /2 / /(/3/) / /(/4/) /BnZr /1/0 / /(/7/)/(d/) Xn / /1 /( Hn /) /2n /5 /= /6 / /(/7/) /BnZr / /(/2/) / /(/5/) /BnZr /5/2 / /(/3/) / /(/4/)/(e/) Xn / /1 /( Hn /) /3n /4 /= /2/3/1/1/6 / /(/7/) /BnZr /5/1/4 / /(/3/) / /(/4/) /+ /2 / /(/2/) / /(/5/)/(f /) Xn / /1 /( Hn /) /4/( n /+ /1/) /3 /= /1/8/5/8 / /(/7/) /BnZr /4/3/2 / /(/3/) / /(/4/) /+ /5 / /(/2/) / /(/5/)/(g/) Xn / /1 /( Hn /) /3n /5 /BnZr /1/1/4 Xn / /1 H /(/2/)nn /6 /= /4/6/9/3/2 / /(/8/) /BnZr /1/6 / /(/3/) / /(/5/) /+ /3/2 / /(/2/) / /(/3/) /2/:T ypical ev aluations of Euler sums/.Euler/, whose in v estigations w ere to b e later com/-pleted b y Nielsen /[/1/9/0/6/]/, disco v ered that the linearsums ha v e ev aluations in terms of zeta v alues inthe follo wing cases/: p /= /1/; p /= q /; p /+ q o dd/; p /+ qev en but with the pair /( p/; q /) b eing restricted to a/nite set of so/-called /\exceptional/" con/gurationsf /(/2 /; /4/) /; /(/4 /; /2/) g /. Of these cases/, the one corresp ond/-ing to p /= q is ob vious giv en the symmetry relationsSp/;q /+ Sq /;p /= / /( p /) / /( q /) /+ / /( p /+ q /) /; (1–2)while the other ones corresp ond to essen tially non/-trivial iden tities/, of whic h examples /(a/)/, /(b/)/, /(c/)at the top of page /1/6 are t ypical/. Rather extensiv en umerical searc h for linear relations b et w een linearEuler sums and p olynomials in zeta v alues /[Baileyet al/. /1/9/9/4/] strongly suggest that Euler found allthe p ossible ev aluations of linear sums/.The next ob jects of in terest are the nonline arsums/, in v olving pro ducts of at least t w o harmonicn um b ers/. Let / /= /( //1 /; /: /: /: /; /k /) b e a partition ofin teger p in to k summands/, so that p /= //1 /+ /
/
/
/+ /k and //1 / //2 / /: /: /: / /k /. The Euler sum of index/ /; q is de/ned b yS/ /;q /= /1Xn /=/1 H /( //1 /)n H /( //2 /)n /
/
/
H /( /k /)nn q /;the quan tit y q /+ //1 /+ /
/
/
/+ /k b eing called the weightand the quan tit y k b eing the de gr e e /. As usual/,rep eated summands in partitions are indicated b yp o w ers/, so that for instanceS/1 /2/2 /3/5 /;q /= S/1/1/2/2/2/5 /;q /= /1Xn /=/1 /( Hn /) /2/( H /(/2/)n /) /3H /(/5/)nn q /:In the past/, a few basic nonlinear sums ha v e b eenev aluated thanks to their relations to the Eule/-rian b eta in tegrals or to p olylogarithms /[de Do elder/1/9/9/1/]/. Recen tly /, a detailed n umerical searc h con/-ducted b y Bailey /, Borw ein/, and Girgensohn /[Baileyet al/. /1/9/9/4/] has rev ealed the existence of man y sur/-prising ev aluations lik e examples /(e/) and /(f /) at thetop of page /1/6/. Some of these ha v e since receiv ed Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 17a due pro of and for instance the pap er /[Borw einet al/. /1/9/9/5/] giv es explicit form ul/ forS/1 /2/;q /= /1Xn /=/1 /( Hn /) /2n qwhenev er the w eigh t q /+ /2 is o dd /(see example /(d/)at the top of page /1/6/)/, and an explicit reduction toS/2 /;q when the w eigh t is ev en/.The situation regarding explicit ev aluations ofEuler sums is at /rst sigh t rather puzzling/. Someev aluations app ear to generalize and form an in//-nite class/|lik e S/1 /2/;q ab o v e/|while others seem tov anish m ysteriously as so on as the w eigh t exceedsa certain threshold/. F or instance/, no /nite for/-m ula in terms of zeta v alues is lik ely to exist forthe cubic sums S/1 /3/;q or the quartic sums S/1 /4/;q ofan o dd w eigh t exceeding /1/0/, while S/1 /3/; /4 /; S/1 /4/; /3 /(ex/-amples /(e/) and /(f /) at the top of page /1/6/) or ev enthe septic S/1 /7/; /2 do reduce to zeta v alues /[Baileyet al/. /1/9/9/4/]/. This suggests the existence of b oth/\general/" classes of ev aluations and /\exceptional/"ev aluations/.A recen t approac h/, exempli/ed b y /[Ho/man /1/9/9/2/;Zagier /1/9/9/4/] sheds a new ligh t on these phenom/-ena/. It is based on considering the multiple zetafunctions de/ned b y/ /( a/1 /; a/2 /; /: /: /: /; al /) /:/= Xn/1 /<n/2 /< /
/
/
/<nl /1n a/1/1 n a/2/2 /
/
/
n all /;where a/1 /+ /
/
/
/+ al is called the weight and l isthe m ultiplicit y /. /(W e follo w here the con v en tionsof /[Zagier /1/9/9/4/; Crandall and Buhler /1/9/9/4/] whileother references/, suc h as /[Borw ein et al/. /1/9/9/5/]/, de/-/ne m ultiple zetas using the opp osite con v en tion/,n/1 /> n/2 /> /
/
/
/> nl /;in summations/. The t w o presen tations are trivialv arian ts of eac h other/, obtained one from the otherb y c hanging the order of the argumen ts/./) Ev eryEuler sum of w eigh t w and degree k is clearly a Q /-linear com bination of m ultiple zeta v alues /(that is/,v alues of m ultiple zeta functions at in teger argu/-men ts/) of w eigh t w and m ultiplicit y at most k /+ /1/. In other w ords/, m ultiple zeta v alues are /\atomic/"quan tities in to whic h Euler sums decomp ose/. Con/-sequen tly /, a complete mo del for the linear relationsin v olving the m ultiple zeta v alues w ould yield a fulldecision pro cedure for determining whether an yparticular Euler sum admits a complete ev aluationin terms of /(single/) zeta v alues/.A conjecture of Zagier/, discussed later/, statesthat the dimension dw of the Q /-linear space gener/-ated b y the /2 w /BnZr /2m ultiple zeta v alues of w eigh t wincreases roughly lik e /1 /: /3/2 w/. In con trast the n um/-b er /w of w eigh t/-homogeneous monomials in zetav alues of w eigh t w is m uc h smaller asymptotically /,b eing only e O /( pw /)/. Th us/, a priori /, only a smallfraction of quan tities expressible in terms of m ul/-tiple zetas should reduce to p olynomials in /(sin/-gle/) zeta v alues/. Ho w ev er/, initially /, the di/erencedw /BnZr /w is small and ev en equal to /0 for some of thelo w w eigh ts/, f /3 /; /4 /; /5 /; /6 /; /7 /; /9 g /. As a consequence/, an yEuler sum of o dd w eigh t at most /9 must reduce tozeta v alues/. The m ultiple zeta mo del therefore ex/-plains w ell the presence of exceptional ev aluationsof Euler sums that app ear in this p ersp ectiv e to b euna v oidable artefacts of lo w w eigh t/.A c haracteristic asp ect of the m ultiple zeta mo delis that it ma y predict r elations but do es not ingeneral pro vide explicit formul/ /. This is where w e/t in/. Our approac h is based on con tour in tegralrepresen tations/. It is directed at Euler sums thatare particular /\nonatomic/" com binations of m ulti/-ple zeta v alues/, ha ving almost complete symmetry /.When applicable/, this approac h do es not requirein v erting collections of linear relations/, whic h ma yb e rather di/cult to do for a whole class of sums asexempli/ed b y /[Borw ein et al/. /1/9/9/5/; Borw ein andGirgensohn /1/9/9/6/]/.Euler sums and m ultiple zetas ha v e connectionswith man y branc hes of mathematics/; see esp ecially/[Zagier /1/9/9/4/]/. Broadh urst /(see /[Borw ein and Gir/-gensohn /1/9/9/6/]/) encoun tered them in relation withF eynman diagrams and asso ciated knots in p er/-turbativ e quan tum /eld theory /. They also surfaceo ccasionally in com binatorial mathematics/: ev alu/-ation /(a/) at the top of page /1/6 serv es to analyze the 18 Experimental Mathematics, Vol. 7 (1998), No. 1distribution of no de degrees in quadtrees /[Fla joletet al/. /1/9/9/5/; Lab elle and Laforest /1/9/9/5/] while alter/-nating Euler sums mak e an app earance in the anal/-ysis of lattice reduction algorithms /[Daud / e et al/./1/9/9/7/]/.The basic tec hniques of this pap er/, b ey ond theCauc h y/{Lindel/ of con tour in tegrals of Lemma /2/./1/,ha v e b een w ork ed out in an exp erimen tal mannerusing the computer algebra system Maple /. Thissystem /\kno ws/" the expansions of all the sp ecialfunctions needed here/, and it has b een used thor/-oughly in order to extract minimal k ernels andsummation form ul//, of whic h those sho wn in theb o x on page /2/4 are t ypical/. Certainly /, the in ten/-siv e computations required b y Section /6 /(see The/-orem /6/./1 and T able /2/) could not ha v e b een carriedout man ually /, in view of the n um b er of equationsin v olv ed/. In return/, the summation form ul/ of thispap er /(lik e those on page /2/4/) could v ery w ell b e en/-capsulated as templates in a general purp ose sum/-mation pac k age/. Section /8 p oin ts in this directionand lists sev eral t yp es of sums that can no w b ecomputed mec hanically using the approac h of thispap er/. 2. GENERAL SUMMATIONSCon tour in tegration is a classical tec hnique for ev al/-uating in/nite sums b y reducing them to a /niten um b er of residue computations/. F or instance/, theeasy iden tit y/2 /1Xn /=/1 /( /BnZr /1/) nn /2/+ /1 /= /2 /e //BnZr e /BnZr / /BnZr /1can b e deriv ed transparen tly from a residue com/-putation of the in tegral/1/2 i/ Z/sin / s dss /2/+ /1o v er a circle cen tred at the origin and whose radiusis tak en arbitrarily large/. The residues at the p oless /= / n with n /6/= /0 generate the left/-hand side ofthe equalit y /, while the p oles at s /= /0 /; / i yield theexplicit form app earing on the righ t/. /(Of course/, man y other tec hniques can b e emplo y ed to deriv ethis iden tit y /, including P oisson/'s summation for/-m ula or Mittag/-Le/er expansions of trigonometricfunctions/./)This summation mec hanism is formalized b y alemma that go es bac k to Cauc h y and is nicely de/-v elop ed throughout /[Lindel/ of /1/9/0/5/]/. W e de/ne akernel function / /( s /) b y the t w o requiremen ts/: / /( s /)is meromorphic in the whole complex plane/; / /( s /)satis/es / /( s /) /= o /( s /) o v er an in/nite collection ofcircles j z j /= /k with /k /! /+ /1 /. Lemma 2.1 (Cauchy, Lindel ¨of). L et / /( s /) b e a kernelfunction and let r /( s /) b e a r ational function whichis O /( s /BnZr /2/) at in/nity /. ThenX/ /2 O Res/( r /( s /) / /( s /)/)s /= / /= /BnZr X/ /2 S Res/( r /( s /) / /( s /)/)s /= / (2–1)wher e S is the set of p oles of r /( s /) and O is the setof p oles of / /( s /) that ar e not p oles of r /( s /)/. Her eRes/( h /( s /)/)s /= / denotes the r esidue of h /( s /) at s /= / /. Proof. It su/ces to apply the residue theorem to/1/2 i/ Z/( /1 /) r /( s /) / /( s /) ds/;where R/( /1 /) denotes in tegration along large circles/,that is/, the limit of in tegrals Rj s j /= /k /. See also thediscussion in /[Henrici /1/9/7/4/, x /4/./9/]/, where a k ernelfunction is called a summatory function/. /This form ula do es ha v e the c haracter of a summa/-tory form ula since the set O of p oles of an irrationalk ernel / /( s /) /(called the /\ordinary p oles/"/) is in/nite/,while the set S of p oles of a rational function r /( s /)/(the /\sp ecial p oles/"/) is necessarily /nite/. W e alsode/ne the sp e cial r esidue sum to b e the /nite sumR /[ / /( s /) r /( s /)/] /:/= X/ /2 S /[f /0 g Res /( / /( s /) r /( s /)/)s /= / /:The amalgamation of /0 to the sp ecial p oles isjust a notational con v enience dictated b y the fre/- Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 19quen t need to isolate /0 in summatory form ul//.Then /(/2/{ /1/) is rephrased asX/ /2 O nf /0 g Res/( r /( s /) / /( s /)/)s /= / /= /BnZr R /[ / /( s /) r /( s /)/] /:Let /[/( s /BnZr / /) r/] h /( s /) denote the co e/cien t of the/( s /BnZr / /) rterm in the Lauren t expansion of h /( s /) ats /= / /. Residues are Lauren t co e/cien ts/, and assuc h they are computable lik e T a ylor co e/cien ts/,sinceRes/( h /( s /)/)s /= / /= /[/( s /BnZr / /) /BnZr /1/] h /( s /)/= /[/( s /BnZr / /) r /BnZr /1/]/( s /BnZr / /) rh /( s /) /;if r is the order of the p ole of h /( s /) at s /= / /. Inother w ords/, the sp ecial residue sum is alw a ys de/-termined b y a few T a ylor series expansions tak enat a /nite collection of p oin ts/.W e mak e here an essen tial use of k ernels in v olv/-ing the / function/. The / function /[Whittak er andW atson /1/9/2/7/] is the logarithmic deriv ativ e of theGamma function/,/ /( s /) /= dds log /BnZr/( s /) /= /BnZr / /BnZr /1s /+ /1Xn /=/1 //1n /BnZr /1n /+ s / (2–2)and it satis/es the complemen t form ula/ /( s /) /BnZr / /( /BnZr s /) /= /BnZr /1s /BnZr / cot / s/;as w ell as an expansion at s /= /0 that in v olv es thezeta v alues/:/ /( s /) /+ / /= /BnZr /1s /+ / /(/2/) s /BnZr / /(/3/) s /2/+ /
/
/
/:(2–3)F rom classical expansions and the prop erties justrecalled of the / function/, one has at an in teger nthe expressions listed on the top of the next page/.Eac h of these functions/, or an y of its deriv ativ es/, isO /( j s j /"/) on circles of radius n /+ /1/2 /(with n a p ositiv ein teger/) cen tred at the origin/. Consequen tly /, an yp olynomial form in/ cot / s/; /sin / s /; / /( j /)/( / s /) (2–4) is itself a k ernel function with p oles at a subset ofthe in tegers/. The purp ose of this pap er is preciselyto in v estigate the p o w er of suc h k ernels in connec/-tion with summatory form ul/ and Euler sums/.W e shall imp ose throughout t w o conditions onthe rational function r /( s /)/:/(i/) r /( s /) is O /( s /BnZr /2/) at in/nit y /,/(ii/) r /( s /) has no p ole in Z n f /0 g /:(2–5)Condition /(i/) is necessary for absolute con v ergenceof the sums/; condition /(ii/) is only a minor tec hnicalrequiremen t/. A direct use of the k ernels of /(/2/{ /4/)then yields the summatory form ul//1Xn /=/1 r /( n /) /= /BnZr R /r /( s /)/( / /( /BnZr s /) /+ / /) //; (2–6)/1Xn /=/1 /( r /( n /) /+ r /( /BnZr n /)/) /= /BnZr R /r /( s /) / cot / s //; (2–7)/1Xn /=/1 /( /BnZr /1/) n/( r /( n /) /+ r /( /BnZr n /)/) /= /BnZr R hr /( s /) /sin / s i/;(2–8)of whic h the last t w o are classical /[Henrici /1/9/7/4/,x /4/./9/]/. The k ernels are / /( /BnZr s /) /+ / /, / cot / s /, and/ /= sin / s /, as is apparen t from the argumen t of thesp ecial residue sum/. Clearly /, equalities /(/2/{ /7/) and/(/2/{ /8/) b ecome trivial if the rational function r /( s /)is o dd/, and suc h parit y phenomena surface recur/-ren tly in Euler sums ev aluation/.A more in teresting k ernel is /( / /( /BnZr s /) /+ / /) /2/, whoseresidues at the p ositiv e in tegers generate harmonicn um b ers since/( / /( /BnZr s /) /+ / /) /2/s /! n /1/( s /BnZr n /) /2 /+ /2 Hn /1s /BnZr n /+ /
/
/
/:In that case/, under the conditions of /(/2/{ /5/)/, w e /nd/2 /1Xn /=/1 r /( n /) Hn /+ /1Xn /=/1 r /0/( n /)/= /BnZr R /r /( s /)/( / /( /BnZr s /) /+ / /) /2 //;(2–9)as results directly from the singular expansion ofthe k ernel /(see b o x at the top of page /2/0/)/. Th us/, 20 Experimental Mathematics, Vol. 7 (1998), No. 1/ cot / s /=s /! n /1s /BnZr n /BnZr /2 /1Xk /=/1 / /(/2 k /)/( s /BnZr n /) /2 k /BnZr /1/sin / s /=s /! n /( /BnZr /1/) n //1/( s /BnZr n /) /+ /2 /1Xk /=/1 /(/1 /BnZr /2 /1 /BnZr /2 k/) / /(/2 k /)/( s /BnZr n /) /2 k /BnZr /1 // /( /BnZr s /) /+ / /=s /! n /1s /BnZr n /+ Hn /+ /1Xk /=/1 /BnZr/( /BnZr /1/) kH /( k /+/1/)n /BnZr / /( k /+ /1/) /
/( s /BnZr n /) k/; if n / /0/ /( /BnZr s /) /+ / /=s /!/BnZr n Hn /BnZr /1 /+ /1Xk /=/1 /BnZrH /( k /+/1/)n /BnZr /1 /BnZr / /( k /+ /1/) /
/( s /+ n /) kif n /> /0/ /( p /BnZr /1/)/( /BnZr s /)/( p /BnZr /1/)/! /=s /! n /1/( s /BnZr n /) p //1 /+ /( /BnZr /1/) p Xi / p /i /BnZr /1p /BnZr /1 //BnZr/ /( i /) /+ /( /BnZr /1/) iH /( i /)n /
/( s /BnZr n /) i /if n / /0 /; p /> /1/ /( p /BnZr /1/)/( /BnZr s /)/( p /BnZr /1/)/! /=s /!/BnZr n /( /BnZr /1/) p Xi / /0 /p /BnZr /1 /+ ip /BnZr /1 //BnZr/ /( p /+ i /) /BnZr H /( p /+ i /)n /BnZr /1 /
/( s /+ n /) iif n /> /0 /; p /> /1/1s q /=s /! n Xj / /0 /( /BnZr /1/) j /q /+ j /BnZr /1q /BnZr /1 //( s /BnZr n /) jn q /+ j if n /6/= /0 /; q /2 Z/+Lo cal expansions of basic k ernels/.b y /(/2/{ /6/)/{/(/2/{ /8/) and /(/2/{ /9/)/, an y sum whose generalterm is the pro duct of the harmonic n um b er Hnand a rational function r /( n /) reduces to a /nite com/-bination of v alues of the / function and its deriv a/-tiv es tak en at a /nite set of p oin ts/. Instan tiatingthis treatmen t to the class of functions r /( s /) /= s /BnZr q/,with q an in teger / /2/, pro duces a form ula alreadykno wn to Euler/. Theorem 2.2 (Euler). F or inte ger q / /2/,S/1 /;q / /1Xn /=/1 Hnn q/= /(/1 /+ q/2 /) / /( q /+ /1/) /BnZr /1/2 q /BnZr /2Xk /=/1 / /( k /+ /1/) / /( q /BnZr k /) /: Proof. A direct consequence of the summatory for/-m ula /(/2/{ /9/) and the expansion /(/2/{ /3/)/. /Sp ecial v alues are giv en in example /(a/) at the topof page /1/6/. The treatmen t just dev elop ed of the simplest Eu/-ler sums is t ypical/. F or the case when r /( s /) /= s /BnZr q/,only one residue needs to b e determined/, and theresidue computation is strictly equiv alen t to a co ef/-/cien t extraction/. Giv en that the k ernels emplo y edthroughout this pap er are p olynomials in / and re/-lated trigonometric functions/, the expressions ob/-tained are in v ariably w eigh t/-homogeneous con v o/-lutions of zeta v alues/. In addition/, the degree ofthe k ernel emplo y ed /(that is itself suggested b y thenature of eac h Euler sum considered/) dictates them ultiplicit y of the con v olution form ul/ that areobtained b y this pro cess/. Alternative ApproachesF ollo wing a suggestion b y a referee/, w e brie/ y dis/-cuss some of the man y approac hes that ha v e b eendev elop ed regarding Euler sums/. P artial fractionexpansions of the Euler/{Nielsen/{Mark ett t yp e /(see/[Nielsen /1/9/0/6/; Mark ett /1/9/9/4/; Borw ein and Girgen/- Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 21sohn /1/9/9/6/]/) are instrumen tal is pro viding r elations /.Iden tities of lo w w eigh t can sometimes b e pro v edb y sp ecial in tegral represen tations and functionalprop erties of p olylogarithms /[de Do elder /1/9/9/1/]/.Amongst more general metho ds/, w e men tion or/-thogonalit y and summatory form ul//. A recen t pa/-p er /[Crandall and Buhler /1/9/9/4/] deriv es the linearrelations of Theorems /2/./2 and /3/./1 using orthogonal/-it y on the unit circle and the p olylogarithmic seriesPn e /2 i/ nx/=n //. This tec hnique is reminiscen t of theP oisson summation form ula/, but the extension toEuler sums of higher degree migh t b e di/cult giv enthe scarcit y of explicit F ourier transforms in v olv/-ing nonlinear forms in the / /-function/. A di/eren tt yp e of orthogonalit y w as suggested b y a refereewho prop osed a Mellin/{P erron t yp e of form ula/,Xn/>m /1n am b /= /1/2 / /( a /+ b /)/= /1/2 i/ Zc /+ i /1c /BnZr i /1 / /( a /BnZr s /) / /( b /+ s /) dss/(for some suitable c /)/. Its p ossible use is ho w ev erstill unclear to us since the in tegrand has only /3p oles at s /= /0/, a /BnZr /1/, /1 /BnZr b /, while ev aluations of Eulersums generally in v olv e more than three terms/.Our pap er is on the other hand v ery close to theEuler/{Maclaurin summation form ula/, esp ecially itscomplex v ersion due to Ab el and Plana /[Henrici/1/9/7/4/, p/. /2/7/4/]/:/1Xn /=/0 f /( n /) /= /1/2 f /(/0/) /+ Z/1/0 f /( x /) dx/+ i Z/1/0 f /( iy /) /BnZr f /( /BnZr iy /)e /2 / y/BnZr /1 dy /:This form ula is pro v ed /[Henrici /1/9/7/4/; Lindel/ of /1/9/0/5/]using the trigonometric k ernel / cot / s in the st yleof Lemma /2/./1/. The goal of this pap er is preciselyto illustrate the v ersatilit y of nonline ar / /-kernelsthat do not seem to ha v e surfaced in the literaturedespite their simplicit y and their p o w er as regardsnonlinear Euler sums/. An instance of this fact isthe solution of the cubic conjectures of /[Bailey et al/. /1/9/9/4/] giv en b y Corollary /5/./2/. Also/, in Theorems /4/./1and /5/./1 and in the b o x on page /2/4/, suc h k ernels arene e de d since purely trigonometric k ernels only giv eaccess to a small subset of Euler sums/, a fact con/-/rmed b y parit y considerations as w ell as b y theclassi/cation of k ernels giv en in Section /6/. 3. LINEAR EULER SUMSNielsen /[/1/9/0/6/]/, elab orating on Euler/'s w ork/, pro v edb y a metho d based on partial fraction expansionsthat ev ery linear sum Sp/;q whose w eigh t p /+ q iso dd is expressible as a p olynomial in zeta v alues/.T o giv e an idea of the metho d /[Nielsen /1/9/0/6/, p/. /5/0/]/,w e sho w that S/1 /; /2 /= /2 / /(/3/)/, an equalit y expressedin terms of double zetas as / /(/1 /; /2/) /= / /(/3/)/. W e ha v e/ /(/1 /; /2/) /= X/0 /<a/<n /1an /2 /= X/0 /<a/<n /1/( n /BnZr a /) n /2/= X/0 /<a/<n /BnZr /1an /2 /+ //1a /2/( n /BnZr a /) /BnZr /1a /2n //= /BnZr / /(/1 /; /2/)/+ X/0 /<a /1a /2 ///1/1 /BnZr /1a /+/1 //+ //1/2 /BnZr /1a /+/2 //+ /
/
/
//;where the second line results from a partial frac/-tion expansion and the last equalit y from series re/-arrangemen ts/. The last sum telescop es and yields/ /(/1 /; /2/) /= /BnZr / /(/1 /; /2/) /+ /BnZr/ /(/1 /; /2/) /+ / /(/3/) /
/:This example is t ypical/. In general the metho dpro vides linear relations b et w een the Sp/;q of thesame w eigh t and quadratic forms in zeta functions/,from whic h a constructiv e /(but not clearly explicit/)reduction to zeta v alues can b e deriv ed/. D/. and J/.Borw ein and R/. Girgensohn /[Borw ein et al/. /1/9/9/5/]ha v e succeeded in /\in v erting/" the Euler/{Nielsen re/-lations b y means of com binatorial matrix decom/-p ositions/. W e sho w here ho w to rederiv e directlythe explicit ev aluations of that pap er/. 22 Experimental Mathematics, Vol. 7 (1998), No. 1 Theorem 3.1 /[Borw ein et al/. /1/9/9/5/]/. F or an o dd weightm /= p /+ q /, the line ar sums ar e r e ducible to zeta val/-ues /,/1Xn /=/1 H /( p /)/( n /)n q/= / /( m /) //1/2 /BnZr /( /BnZr /1/) p/2 /m /BnZr /1p //BnZr /( /BnZr /1/) p/2 /m /BnZr /1q / //+ /1 /BnZr /( /BnZr /1/) p/2 / /( p /) / /( q /)/+/( /BnZr /1/) p b p/= /2 cXk /=/1 /m /BnZr /2 k /BnZr /1q /BnZr /1 // /(/2 k /) / /( m /BnZr /2 k /)/+/( /BnZr /1/) p b q /= /2 cXk /=/1 /m /BnZr /2 k /BnZr /1p /BnZr /1 // /(/2 k /) / /( m /BnZr /2 k /) /;wher e / /(/1/) should b e interpr ete d as /0 wher ever ito c curs /. Proof. In the con text of this pap er/, the theoremresults from applying the k ernel/1/2 / cot /( / s /) / /( p /BnZr /1/)/( /BnZr s /)/( p /BnZr /1/)/! /;to the base function r /( s /) /= s /BnZr q/. The only singular/-ities are p oles at the in tegers/. A t a negativ e in teger/BnZr n the p ole is simple and the residue is/( /BnZr /1/) m/2 n q // /( p /) /BnZr H /( p /)n /+ /1n p //:A t a p ositiv e in teger n /, the p ole has order p /+ /1and the residue is/1/2 n q /( H /( p /)n /BnZr / /( p /)/) /+ /( /BnZr /1/) p /m /BnZr /1p //1/2 n m/+ /1 /+ /( /BnZr /1/) p/2 n q / /( p /) /BnZr /( /BnZr /1/) p b p/= /2 cXk /=/1 /m /BnZr /2 k /BnZr /1p /BnZr /2 k // /(/2 k /)n m /BnZr /2 k /: Finally the residue of the p ole of order m /+ /1 at /0is found to b e/( /BnZr /1/) p/2 /m /BnZr /1q // /( m /)/+ /( /BnZr /1/) p /+/1 b q /= /2 cXk /=/1 /m /BnZr /2 k /BnZr /1p /BnZr /1 // /(/2 k /) / /( m /BnZr /2 k /) /:Summing these three con tributions yields the state/-men t of the theorem/. /F or ev en w eigh ts/, a mo di/ed form of the iden tit yholds/, but without an y linear Euler sum o ccurring/.This giv es bac k w ell/-kno wn nonlinear relations b e/-t w een zeta v alues at ev en argumen ts/. In this caseof ev en w eigh t w /, there also exist relations b et w eenlinear sums/. The k ernels/j /( s /) /= /BnZr/ /( j /)/( /BnZr s /) /
/2(3–1)applied to s /BnZr qyield further relations/. /(F or j /= /1 /; /2/,the general summation form ul/ are giv en in /( S/4 /)and /( S/5 /) of the b o x on page /2/4/./) When sp ecializedto r /( s /) /= s /BnZr q/, the k ernel /j yields linear relationsb et w eenS/2 j /+/1 /;q /; S/2 j/;q /+/1 /; /: /: /: /; Sj /+/1 /;q /+ j (3–2)and p olynomials in zeta v alues that are of a shap esimilar to the Euler/{Nielsen relations/. This giv esthe reductionsS/3 /;q /7/! S/2 /;q /+/1 /;S/5 /;q /7/! f S/2 /;q /+/3 /; S/4 /;q /+/1 g /;S/7 /;q /7/! f S/2 /;q /+/5 /; S/4 /;q /+/3 /; S/6 /;q /+/1 g /;and so on/. Suc h relations are to b e complemen tedb y the symmetry relations /(/1/{ /1/)/.Iden tit y /(c/) in the b o x of page /1/6 is an ev alua/-tion that is t ypical of o dd w eigh t iden tities/. F orthe exceptional ev en w eigh ts f /4 /; /6 g /, the symmetry Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 23relations giv e S/2 /; /2 and S/3 /; /3 /, whence/, b y /( S/4 /) /; /( S/5 /)of page /2/4/, all linear sums/,/1Xn /=/1 H /(/2/)nn /2 /= /7/4 / /(/4/) /;/1Xn /=/1 H /(/3/)nn /3 /= /1/2 / /2/(/3/) /+ /1/2 / /(/6/) /;/1Xn /=/1 H /(/2/)nn /4 /= / /(/3/) /2/BnZr /1/3 / /(/6/) /:F or the next ev en w eigh ts/, w e obtain relations fromwhic h it results/, again in conjunction with the sym/-metry relations/, that the setsf S/2 /; /6 g /; f S/2 /; /8 g /; f S/2 /; /1/0 g /; f S/2 /; /1/2 /; S/4 /; /1/0 gare su/cien t to express linearly all linear sums ofw eigh ts /8 /; /1/0 /; /1/2 /; /1/4 /(mo dulo zeta v alues/)/. F or in/-stance/, w e ha v e the relations/5 /1Xn /=/1 H /(/2/)nn /6 /+ /2 /1Xn /=/1 H /(/3/)nn /5 /= /BnZr /2/1/4 / /(/8/) /+ /1/0 / /(/3/) / /(/5/) /;/7 /1Xn /=/1 H /(/2/)nn /8 /+ /2 /1Xn /=/1 H /(/3/)nn /7 /= /BnZr /3/3/2 / /(/1/0/)/+/1/4 / /(/3/) / /(/7/) /+ /8 / /(/5/) /2/;/7 /1Xn /=/1 H /(/2/)nn /8 /BnZr /2 /1Xn /=/1 H /(/4/)nn /6 /= /BnZr /2/2/7/1/0 / /(/1/0/)/+/1/4 / /(/3/) / /(/7/) /+ /1/0 / /(/5/) /2/:Zagier /[/1/9/9/4/]/, b y means of an analogy with thetheory of mo dular forms/, and Borw ein et al/. /[/1/9/9/5/]/,b y exploiting directly the Euler/{Nielsen relations/,ha v e sho wn that the linear relations of ev en w eigh tdetermine all but b /( w /BnZr /2/) /= /6 c of the linear Eulersums that are th us considered to b e /\new/" con/-stan ts/. Note on the choice of kernels. The k ernels are ratherdirectly related to the quan tities sub ject to sum/-mation/. As w e ha v e seen/, the residues of /( / /( /BnZr s /) /+/ /) /2generate the harmonic n um b ers/, so that sumsin v olving Hn should b e represen ted b y in tegralsin v olving this k ernel/, in accordance with /( S/3 /) ofpage /2/4/. The k ernel / /0/( /BnZr s /) /2similarly in tro duces H /(/2/)n and H /(/3/)n and th us generates relation /( S/4 /) thatin v olv es t w o t yp es of harmonic n um b ers/. F urther/-more/, b y com bining form ul/ for r /( s /) and r /( /BnZr s /)/,the terms in v olving H /(/3/)n disapp ear when r /( s /) is ano dd function/; the use of / cot / s as replacemen tfor one factor of / /0/( /BnZr s /) precisely has the e/ect ofac hieving suc h a com bination/. Th us a sum lik ePH /(/2/)n r /( n /) b ecomes reducible when r /( s /) is an o ddfunction/. Similar observ ations dictate the c hoice ofk ernels throughout this pap er as is illustrated b ythe b o xes on pages /2/4 and /2/6/. 4. QUADRATIC EULER SUMSStarting from an observ ation of E/. Au/-Y eung thatS/1 /2/; /2 /= /1Xn /=/1 /( Hn /) /2n /2 /= /1/7/4 / /(/4/) /;Borw ein et al/. /[/1/9/9/5/] ha v e giv en a general reductionof the quadratic sums S/1 /2/;q to double sums/, whic hin turn en tails a complete ev aluation in terms ofsingle zeta v alues for o dd w eigh t/. These sums areclosely related to deriv ativ es of the Eulerian b etain tegral/. W e sho w here a direct deriv ation of thereductions b y means of / k ernels that pro vides inpassing general summatory form ul/ for sums in/-v olving /( Hn /) /2/. /(See also the b o x on page /2/4 andSection /8/./) Theorem 4.1 /[Borw ein et al/. /1/9/9/5/]/. F or al l weights /,the quadr atic sums S/1 /2/;q r e duc e to line ar sums andp olynomials in zeta values /:S/1 /2/;q /BnZr S/2 /;q /= q S/1 /;q /+/1 /BnZr q /( q /+ /1/)/6 / /( q /+ /2/) /+ / /(/2/) / /( q /) /: Proof. The pro of is based on the cubic k ernel/ /( s /) /= /( / /( /BnZr s /) /+ / /) /3and the usual residue computation/. When appliedto an arbitrary rational function r /( s /) satisfying/(/2/{ /5/)/, it yields the summatory form ula /( S/7 /) in theb o x on page /2/4/. The sp ecialization to r /( s /) /= s /BnZr qgiv es the statemen t/. / 24 Experimental Mathematics, Vol. 7 (1998), No. 1/( S/1 /) /1Xn /=/1 r /( n /) /= /BnZr R /r /( s /)/( / /( /BnZr s /) /+ / /) //( S/2 /) /2 /1Xn /=/1 r/0 /( n /) /= /BnZr R /r/0 /( s /) / cot / s //( S/3 /) /2 /1Xn /=/1 r /( n /) Hn /+ /1Xn /=/1 r /0/( n /) /= /BnZr R /r /( s /)/( / /( /BnZr s /) /+ / /) /2 //( S/4 /) /BnZr /4 /1Xn /=/1 H /(/3/)n r /( n /) /+ /2 /1Xn /=/1 H /(/2/)n r /0/( n /) /+ /1Xn /=/1 /BnZr/4 / /(/3/) r /( n /) /+ /2 / /(/2/) r /0/( n /) /+ /1/6 r /0/0/0/( n /) /
/= /BnZr R /r /( s /)/( / /0/( /BnZr s /)/) /2 //( S/5 /) /4/8 /1Xn /=/1 H /(/5/)n r /( n /) /BnZr /2/4 /1Xn /=/1 H /(/4/)n r /0/( n /) /+ /4 /1Xn /=/1 H /(/3/)n r /0/0/( n /)/+ /1Xn /=/1 /BnZr/BnZr /4/8 / /(/5/) r /( n /) /BnZr /2/4 / /(/4/) r /0/( n /) /BnZr /4 / /(/3/) r /0/0/( n /) /+ /1/3/0 r /( v /)/( n /) /
/= /BnZr R /r /( s /)/( / /0/0/( /BnZr s /)/) /2 //( S/6 /) /2 /1Xn /=/1 H /(/2/)n r/1 /( n /) /+ /1Xn /=/1 //1/2 r /0/0/1 /( n /) /BnZr /2 / /(/2/) r/1 /( n /) /BnZr r/1 /( n /)n /2 //= /BnZr R /r/1 /( s /) / /0/( /BnZr s /) / cot /( / s /) //( S/7 /) /3 /1Xn /=/1 r /( n /)/( Hn /) /2/BnZr /3 /1Xn /=/1 r /( n /) H /(/2/)n /+ /3 /1Xn /=/1 Hn r /0/( n /) /+ /1Xn /=/1 /BnZr/1/2 r /0/0/( n /) /BnZr /3 r /( n /) / /(/2/) /
/= /BnZr R /r /( s /)/( / /( /BnZr s /) /+ / /) /3 /General summatory form ul/ resulting from k ernels /(last column/) that are p olynomial forms in / functions/.Here r /( s /)/, r/0 /( s /)/, and r/1 /( s /) denote rational functions that satisfy the conditions or /(/2/{/5/)/, with additionally r/0 /( s /)ev en and r/1 /( s /) o dd/. Cubic form ul/ are giv en in the pro of of Theorem /5/./1/.In Theorem /4/./1/, for ev en w eigh ts / /8/, only S/1 /;q /+/1reduces to zeta v alues/. F or o dd w eigh ts/, b oth S/1 /;q /+/1and S/2 /;q reduce to zeta v alues/, hence a completeev aluation/. W e ha v e/, for small o dd w eigh t/,/1Xn /=/1 /( Hn /) /2n /3 /= /7/2 / /(/5/) /BnZr / /(/2/) / /(/3/) /;/1Xn /=/1 /( Hn /) /2n /5 /= /6 / /(/7/) /BnZr / /(/2/) / /(/5/) /BnZr /5/2 / /(/3/) / /(/4/) /;/1Xn /=/1 /( Hn /) /2n /7 /= /5/5/6 / /(/9/) /BnZr / /(/2/) / /(/7/)/BnZr /7/2 / /(/3/) / /(/6/) /BnZr /5/2 / /(/4/) / /(/5/) /+ /1/3 / /(/3/) /3/;and for small ev en w eigh t/, /1Xn /=/1 H /2nn /6 /BnZr /1Xn /=/1 H /( /2 /)nn /6 /= /9/1/1/2 / /( /8 /) /BnZr /8 / /( /3 /) / /( /5 /) /+ / /( /2 /) / /( /3 /) /2/;/1Xn /=/1 H /2nn /8 /BnZr /1Xn /=/1 H /( /2 /)nn /8 /= /4/7/3/4/0 / /( /1/0 /) /BnZr /1/0 / /( /3 /) / /( /7 /) /BnZr /5 / /( /5 /) /2/+ / /( /4 /) / /( /3 /) /2/+ /2 / /( /2 /) / /( /3 /) / /( /5 /) /;with the follo wing exceptional ev aluations for thew eigh ts f /4 /; /6 g /:/1Xn /=/1 /( Hn /) /2n /2 /= /1/7/4 / /(/4/) /;/1Xn /=/1 /( Hn /) /2n /4 /= /9/7/2/4 / /(/6/) /BnZr /2 / /(/3/) /2/:(4–1) Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 25A /= /( /BnZr /1/) p/1 /+ p/2/ /( p/1 /) / /( p/2 /) / /( q /) /+ /( /BnZr /1/) p/1/ /( p/1 /) Sp/2 /;q /+ /( /BnZr /1/) p/2/ /( p/2 /) Sp/1 /;qB /= Xi /+ j /+/2 k /= p/1 /( /BnZr /1/) j /j /+ q /BnZr /1q /BnZr /1 / /p/2 /+ i /BnZr /1p/2 /BnZr /1 //BnZr/( /BnZr /1/) p/2 /+ iSp/2 /+ i/;q /+ j /+ / /( p/2 /+ i /) / /( q /+ j /) /
/ /(/2 k /)C /= Xi /+ j /+/2 k /= p/2 /( /BnZr /1/) j /j /+ q /BnZr /1q /BnZr /1 / /p/1 /+ i /BnZr /1p/1 /BnZr /1 //BnZr/( /BnZr /1/) p/1 /+ iSp/1 /+ i/;q /+ j /+ / /( p/1 /+ i /) / /( q /+ j /) /
/ /(/2 k /)D /= Xj /+/2 k /= p/1 /+ p/2 /( /BnZr /1/) j /j /+ q /BnZr /1q /BnZr /1 // /(/2 k /) / /( q /+ j /)E /= /( /BnZr /1/) p/1 /+ p/2 /+ q /BnZr/BnZr Sp/1 /;p/2 /+ q /BnZr Sp/2 /;p/1 /+ q /BnZr / /( p/1 /) Sp/2 /;q /BnZr / /( p/2 /) Sp/1 /;q/+ / /( p/1 /+ p/2 /+ q /) /+ / /( p/1 /+ q /) / /( p/2 /) /+ / /( p/2 /+ q /) / /( p/1 /) /+ / /( p/1 /) / /( p/2 /) / /( q /) /
F /= / /( p/1 /+ p/2 /+ q /) /+ /( /BnZr /1/) p/2 Xi /+/2 k /= p/1 /+ q /p/2 /+ i /BnZr /1p/2 /BnZr /1 // /( p/2 /+ i /) / /(/2 k /)/+/( /BnZr /1/) p/1 Xi /+/2 k /= p/2 /+ q /p/1 /+ i /BnZr /1p/1 /BnZr /1 // /( p/1 /+ i /) / /(/2 k /)/+/( /BnZr /1/) p/1 /+ p/2 Xi/1 /+ i/2 /+/2 k /= q /p/1 /+ i/1 /BnZr /1p/1 /BnZr /1 //p/2 /+ i/2 /BnZr /1p/2 /BnZr /1 // /( p/1 /+ i/1 /) / /( p/2 /+ i/2 /) / /(/2 k /) /:The summands in the ev aluation of Theorem /4/./2/.The sum S/1 /2/;q is also related to the triple zetafunction / /(/1 /; /1 /; q /) sinceS/1 /2/;q /BnZr Sq /; /2 /= /2 / /(/1 /; /1 /; q /) /BnZr / /( q /+ /2/) /+ Sq /+/1 /; /1 /;as sho wn b y an elemen tary computation/. Th us/, thestatemen t is equiv alen t to a reduction of / /(/1 /; /1 /; q /)to double zetas/. General quadratic sumsA more general reduction results from the k ernel/ /( p/1 /BnZr /1/)/( /BnZr s /)/( p/1 /BnZr /1/)/! / /( p/2 /BnZr /1/)/( /BnZr s /)/( p/2 /BnZr /1/)/! / cot / s/; (4–2)but it in v olv es a parit y restriction on the w eigh tb ecause of its trigonometric factor/. Theorem 4.2. If p/1 /+ p/2 /+ q is even /, and p/1 /> /1/,p/2 /> /1/, q /> /1/, the quadr atic sumsSp/1 p/2 /;q /= Xn / /1 H /( p/1 /)n H /( p/2 /)nn q ar e r e ducible to line ar sums /. We have/BnZr/( /BnZr /1/) p/1 /+ p/2 /+ q/+ /1 /
Sp/1 p/2 /;q/= /BnZr A /+ /2/( /BnZr /1/) p/2B /+ /2/( /BnZr /1/) p/1C /+ /2 D /BnZr E /+ /2 F /;wher e the quantities A/; B /; C /; D /; E /; F ar e de/ne d inthe b ox ab ove and the sums ar e over al l indic es / /0/.The value / /(/0/) /= /BnZr /1/2 should b e use d and / /(/1/) shouldb e r eplac e d by /0 whenever it o c curs /. Proof. Use the k ernel of /(/4/{ /2/)/. The quan tit y Frepresen ts/BnZr R /s /BnZr q / /( p/1 /BnZr /1/)/( /BnZr s /)/( p/1 /BnZr /1/)/! / /( p/2 /BnZr /1/)/( /BnZr s /)/( p/2 /BnZr /1/)/! / cot / s //;that is estimated as a T a ylor co e/cien t/. The otherquan tities represen t com bined con tributions of thep oles at s /= / n /. /A similar/, and sligh tly simpler/, expression holdswhen either i /= /1 or j /= /1/, in whic h case one shouldreplace / /(/0/)/( /BnZr s /) b y / /( /BnZr s /) /+ / /. 26 Experimental Mathematics, Vol. 7 (1998), No. 1Kernel Reduction Order/( / /( /BnZr s /) /+ / /) /2S/1 /;r /1 Reduction/, all r /(Thm/. /2/./2/)/ /( p /BnZr /1/)/( /BnZr s /) / cot / s Sp/;q /1 Reduction/, o dd w eigh t p /+ q /(Thm/. /3/./1/)/( / /( j /)/( /BnZr s /)/) /2S/2 j /+/1 /;q /; /: /: /: /; Sj /+/1 /;q /+ j /1 Relations/, ev en w eigh t /(Eqs/. /(/3/{ /1/)/, /(/3/{ /2/)/)/( / /( /BnZr s /) /+ / /) /3S/1 /2/;q /BnZr S/2 /;q /2 Reduction/, an y w eigh t/ /( i /BnZr /1/)/( /BnZr s /) / /( j /BnZr /1/)/( /BnZr s /) / cot / s Sij/;k /7/! f Sa/;b g /2 Reduction of order/, ev en w eigh t /(Thm/. /4/./2/)/( / /( /BnZr s /) /+ / /) /4S/1 /3/;q /BnZr /3 S/1 /2 /;q /3 Reduction/, an y w eigh t /(Thm/. /5/./1/) TABLE 1. A summary of k ernels and the corresp onding reductions/.As is w ell kno wn/, the m ultiple zeta functions sat/-isfy shu/e r elations that generalize the symmetryrelation /(/1/{ /2/)/. F or instance/,/ /( a /) / /( b/; c /) /= / /( a/; b/; c /) /+ / /( a /+ b/; c /) /+ / /( b/; a/; c /)/+ / /( b/; a /+ c /) /+ / /( b/; c/; a /)(4–3)for a /> /1 and c /> /1/, as seen b y considering allw a ys of in terlacing the v ector argumen ts /( a /) and/( b/; c /)/. The conjunction of the theorem and sh uf/-/ e relations/, pro vides a simple pro of of /\half /" ofthe main result of /[Borw ein and Girgensohn /1/9/9/6/]/,according to whic h all triple zeta v alues of ev enw eigh t are reducible to double zeta v alues/. Thereductions obtained are in addition explicit doublecon v olutions of simple and double zeta v alues/. Corollary 4.3 /[Borw ein and Girgensohn /1/9/9/6/]/. F orc /> /1/, triple zeta values / /( a/; b/; c /) whose weight a /+b /+ c is even ar e r e ducible to double zeta values ore quivalently to line ar Euler sums /. Proof. It su/ces to consider the trivially mo di/edquadratic sumsT /( i/; j/; k /) /:/= /1Xn /=/1 H /( i /)n /BnZr /1 H /( j /)n /BnZr /1 /1n k/= Sij/;k /BnZr Sj/;k /+ i /BnZr Si/;k /+ j /+ / /( i /+ j /+ k /)/= / /( i/; j/; k /) /+ Si /+ j/;k /+ / /( j/; i/; k /) /:Assume /rst that j /> /1/; k /> /1 is gran ted/. Then/,from the sh u/e relations with a /= k /, b /= i /, andc /= j /, w e /nd / /( i/; j/; k /) /= / /( k /) / /( i/; j /) /BnZr / /( k /+ i/; j /) /BnZr / /( i/; k /+ j /)/BnZr /BnZr/ /( k /; i/; j /) /+ / /( i/; k /; j /) /
/= / /( k /) / /( i/; j /) /BnZr / /( k /+ i/; j /) /BnZr / /( i/; k /+ j /)/BnZr /BnZrT /( i/; j/; k /) /BnZr / /( i /+ j/; k /) /BnZr / /( i /+ j /+ k /) /
/:The dual case when i /> /1 is treated b y the substi/-tutions a /= k /, b /= j /, and c /= i /. If b oth i and jequal /1/, then the reduction is attained b y the com/-putation of S/1 /2/;k /. /It is b eliev ed that no reduction holds in general fortriple zetas of o dd w eigh ts /[Borw ein and Girgen/-sohn /1/9/9/6/]/. Actually /, starting at /(o dd/) w eigh t /1/1/,it seems that / /(/5 /; /3 /; /3/) is indep enden t of single zetav alues/. /(Suc h prop erties can b e approac hed heuris/-tically b y means of linear in teger dep endency algo/-rithms based on lattice reduction or related tec h/-niques/./) Ho w ev er/, for the exceptional o dd w eigh tsf /5 /; /7 /; /9 g /, all triple zeta v alues are no w kno wn tob e reducible to p olynomials in single zetas/: thisis the other /\half /" of the main result of /[Borw einand Girgensohn /1/9/9/6/] already referred to that w eextend a little bit further in Section /6/. An indirectconsequence to b e discussed in the next section isthe reduction of the cubic sums S/1 /3/;q corresp ondingto sp ecial quadruple zeta v alues/. 5. CUBIC AND HIGHER ORDER EULER SUMSF or higher degree sums/, lik e the cubicS/1 /3/;q /:/= /1Xn /=/1 /( Hn /) /3n q /; Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 27it is natural to consider the k ernels /( / /( /BnZr s /) /+ / /) /4and /( / /( /BnZr s /) /+ / /) /3/ cot / s /. Cross pro ducts start toproliferate but the relations obtained at the previ/-ous steps help reduce man y of the sums/. Theorem 5.1. /(i /) F or o dd weights /, the cubic c ombi/-nation S/1 /3/;q /BnZr /3 S/1 /2 /;q is expr essible in terms ofzeta values /./(ii /) F or even weights /, b oth S/1 /3/;q and S/1 /2 /;q ar e r e/-ducible to S/2 /;q /+/1 and to p olynomials in zeta val/-ues /. Proof. Let r /( s /) /; r/1 /( s /) satisfy the conditions of /(/2/{ /5/)/,and supp ose additionally that r/1 /( s /) is o dd/. Thena direct residue computation giv es/BnZr R //( / /( /BnZr s /) /+ / /) /4r /( s /) //= /4 /1Xn /=/1 r /( n /) /BnZr/( Hn /) /3/BnZr /3 Hn H /(/2/)n /
/+ /6 /1Xn /=/1 r /0/( n /)/( Hn /) /2/+ /1Xn /=/1 /4 /BnZrH /(/3/)n /BnZr /3 / /(/2/) Hn /BnZr / /(/3/) /
r /( n /)/BnZr /4 /1Xn /=/1 /BnZrH /(/2/)n /+ / /(/2/) /
r /0/( n /) /+ /2 Hn r /0/0/( n /) /+ r /0/0/0/( n /)/6and/BnZr R //( / /( /BnZr s /) /+ / /) /3/ cot /( / s /) r/1 /( s /) //= /BnZr /6 /1Xn /=/1 r/1 /( n /) Hn H /(/2/)n /+ /3 /1Xn /=/1 /( Hn /) /2 /r/1 /( n /)n /+ r /0/1 /( n /) //+ /3 /1Xn /=/1 /H /(/3/)n /BnZr //4 / /(/2/) /+ /1n /2 /Hn /BnZr / /( /3 /) /+ /1/3 n /3 /r/1 /( n /)/BnZr /1Xn /=/1 /BnZr/3 H /(/2/)n /+ /5 / /(/2/) /
r /0/1 /( n /) /+ /3/2 Hn r /0/0/1 /( n /) /+ r /0/0/0/1 /( n /)/6These form ul/ complemen t the ones in the b o x onpage /2/4/.Instan tiating the /rst iden tit y to r /( s /) /= s /BnZr qwithev en q and app ealing to relations /( S/4 /)/, /( S/6 /) and/( S/7 /) of page /2/4 yields the /rst part of the theo/-rem/. The second iden tit y is an explicit v ersion ofthe quadratic reductions discussed in the previoussection/; it p ermits to disp ose of the sum S/1 /2 /;q that reduces to the linear sums S/2 /;q /+/1 for ev en w eigh t/.Instan tiating it to r /( s /) /= s /BnZr qwith o dd q yields thesecond part of the theorem/. /F or ev en w eigh t/, w e th us ha v e an in/nite collectionof explicit reductions/, including some that w erepresen ted as conjectural in T able /4 of /[Bailey et al/./1/9/9/4/]/:/1Xn /=/1 /( Hn /) /3n /5 /BnZr /1/1/4 /1Xn /=/1 H /( /2 /)nn /6 /= /4/6/9/3/2 / /( /8 /) /BnZr /1/6 / /( /3 /) / /( /5 /)/+ /3/2 / /( /2 /) / /( /3 /) /2/;/1Xn /=/1 /( Hn /) /3n /7 /BnZr /1/3/4 /1Xn /=/1 H /( /2 /)nn /8 /= /5/6/1/2/0 / /( /1/0 /) /BnZr /4/7/4 / /( /5 /) /2/BnZr /4/9/2 / /( /7 /) / /( /3 /) /+ /3 / /( /2 /) / /( /3 /) / /( /5 /) /+ /1/5/4 / /( /3 /) /2/ /( /4 /) /;/1Xn /=/1 /( Hn /) /3n /9 /BnZr /1/5/4 /1Xn /=/1 H /( /2 /)nn /1/0 /= /1/0/6/0/3/4/5/2/2/1/1/2 / /( /1/2 /)/BnZr /3/3 / /( /5 /) / /( /7 /) /BnZr /3/5 / /( /3 /) / /( /9 /) /BnZr /1/4 / /( /3 /) /4/+ /3/2 / /( /2 /) / /( /5 /) /2/+ /2/1/4 / /( /3 /) /2/ /( /6 /) /+ /1/5/2 / /( /3 /) / /( /4 /) / /( /5 /) /+ /3 / /( /2 /) / /( /3 /) / /( /7 /) /: Corollary 5.2. The cubic sums S/1 /3/;q of weights f /5 /; /6 /;/7 /; /9 g ar e r e ducible to zeta values /:/1Xn /=/1 /( Hn /) /3/( n /+ /1/) /2 /= /1/5/2 / /(/5/) /+ / /(/2/) / /(/3/) /;/1Xn /=/1 /( Hn /) /3/( n /+ /1/) /3 /= /BnZr /3/3/1/6 / /(/6/) /+ /2 / /(/3/) /2/;/1Xn /=/1 /( Hn /) /3/( n /+ /1/) /4 /= /1/1/9/1/6 / /(/7/) /BnZr /3/3/4 / /(/3/) / /(/4/) /+ /2 / /(/2/) / /(/5/) /;/1Xn /=/1 /( Hn /) /3/( n /+ /1/) /6 /= /1/9/7/2/4 / /(/9/) /BnZr /3/3/4 / /(/4/) / /(/5/)/BnZr /3/7/8 / /(/3/) / /(/6/) /+ / /(/3/) /3/+ /3 / /(/2/) / /(/7/) /:/(The forms giv en are those of /[Bailey et al/. /1/9/9/4/]/./) Proof. W e only indicate brie/ y the c hain of reduc/-tions/. F or w eigh t /6/, this results from the ev aluationof S/2 /; /4 in /(/4/{ /1/)/. F or w eigh t /5/, the ev aluation follo wsfrom Ho/man/'s /[Ho/man /1/9/9/2/] complete reductionof m ultiple zetas in the case of all w eigh ts / /6/. F orthe o dd w eigh ts f /7 /; /9 g /, the reduction follo ws from 28 Experimental Mathematics, Vol. 7 (1998), No. 1the Borw ein/{Girgensohn result after whic h triplezetas are reducible to double and single zetas forall w eigh ts / /1/0/. Alternativ ely /, one ma y use reduc/-tion b y an y maximal system of relations presen tedin Section /6/. / Higher Degree Euler SumsLinear Euler sums reduce to zeta v alues in the caseof an o dd w eigh t/, while quadratic Euler sums re/-duce to linear sums /(double zeta v alues/) in the caseof an ev en w eigh t/. W e pro v e here a result to thee/ect that suc h reductions of order are general/. Theorem 5.3. /(i /) F or o dd weight w /= i /+ j /+ k /+ l /,al l cubic sums Sij k /;l r e duc e to c ombinations ofEuler sums of or der at most /2/./(ii /) Mor e gener al ly /, a nonline ar Euler sumSi/1 i/2 /
/
/
ir /;qr e duc es to a c ombination of sums of lower or derswhenever the weight i/1 /+ i/2 /+ /
/
/
/+ ir /+ q and theor der r ar e of the same p arity /. Proof. W e start with the case of cubic sums andadopt the k ernel/i/;j/;k /= /1/( i /BnZr /1/)/! /( j /BnZr /1/)/! /( k /BnZr /1/)/!/ / /( i /BnZr /1/)/( /BnZr s /) / /( j /BnZr /1/)/( /BnZr s /) / /( k /BnZr /1/)/( /BnZr s /) / cot / s/;whic h is applied to r /( s /) /= s /BnZr l/. The expansion ats /= m /,/1/( i /BnZr /1/)/! / /( i /BnZr /1/)/( /BnZr s /) /= /1/( s /BnZr m /) i /+ H /( i /)m /+ /( /BnZr /1/) i/ /( i /) /+ /
/
/
/;implies that the sum of residues at p ositiv e in tegersis of the form Sij k /;l /+ T /, where T is a com binationof quadratic sums/. The expansion at s /= /BnZr m /,/1/( i /BnZr /1/)/! / /( i /BnZr /1/)/( /BnZr s /) /= /( /BnZr /1/) i /BnZr /1 /BnZrH /( i /)m /BnZr /1 /BnZr / /( i /) /
/+ /
/
/
/;implies that the sum of residues at negativ e in te/-gers is of the form /( /BnZr /1/) i /+ j /+ k /+ l /BnZr /3Sij k /;l /+ U /, where Uis a com bination of quadratic sums/. W e th us ha v ea reduction of order whenev er the w eigh t is o dd/. The general case follo ws along the v ery samelines/. /Broadh urst has made a conjecture /(see /[Borw einand Girgensohn /1/9/9/6/]/) of a shap e similar to ourstatemen t but concerning m ultiple zeta v alues in/-stead/. In the case of quadratic sums/, w e ha v e atleast seen that the sh u/e relations en tail a cor/-resp onding reduction for all triple zeta v alues/. Itdo es not seem that Broadh urst/'s conjecture can b ededuced/, ev en partially /, from our theorem/. 6. MODELS OF EULER SUM IDENTITIESV arious approac hes ha v e b een dev elop ed for Eulersums ev aluations/. W e discuss here general metho dsand lea v e aside metho ds based on de/nite in tegralsand p olylogarithms of whic h De Do elder/'s pap er/[/1/9/9/1/] is t ypical/. Our purp ose here is to obtaincomplete mo dels for lo w w eigh ts and at the sametime examine the p o w er of v arious framew orks pro/-p osed/, including the residue metho d/. Shuffle RelationsThese are relations that generalize the symmetryrelation /(sh u/e of order /2/) of /(/1/{ /2/) and the partic/-ular sh u/e of order /3 of /(/4/{ /3/)/. Consideration of thepro duct of t w o m ultiple zeta functions / /( u /) /; / /( v /)/,with u /; v denoting arbitrary v ectors of in tegers/,giv es the relation/ /( u /) /
/ /( v /) /= Xw /2 u x v / /( w /) /; (6–1)where /( u x v /) is the shu/e of v ectors u /; v /, that is/,the set of v ectors de/ned recursiv ely b y/( a /
u /) x /( b /
v /)/= a /
/BnZru x /( b /
v /) /
/[ b /
/BnZr/( a /
u /) x v /
/[ /( a /+ b /) /
/( u x v /) /:Here the dot op eration is the concatenation of v ec/-tors /(extended to sets in the usual w a y/) and allop erations are tak en in the sense of m ultisets so asto preserv e m ultiplicities/.Equation /(/6/{ /1/) simply expresses all p ossible in/-terlacings of indices when a pro duct is expanded b y Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 29distributivit y /. The sh u/e relations are similar tosymmetric function iden tities studied b y Ho/man/[/1/9/9/2/] and/, as noted b y Zagier /[/1/9/9/4/]/, they implythat the linear space spanned b y the m ultiple zetav alues forms a ring/.W e denote b y / the set of linear relations thatarise from sh u/es/. DualityDualit y is a surprising prop ert y /rst conjectured in/[Ho/man /1/9/9/2/] and pro v ed in /[Zagier /1/9/9/4/] up on asuggestion of Kon tsevic h/. It is expressed b y meansof an enco ding b y binary v ectors of m ultiple zetav alues/: giv en a v ector u /= /( u/1 /; /: /: /: /; uk /)/, its enco dingis/ /( u/1 /; u/2 /; /: /: /: /; uk /) /:/= /1/0 u/1 /BnZr /1/1/0 u/2 /BnZr /1/
/
/
/1/0 uk /BnZr /1/;where /0 kmeans /0 rep eated k times/. W e then in/-tro duce the quan titiesH /( U /) /:/= / /( / /( /BnZr /1/)U /) /;that are de/ned for all binary v ectors starting witha /1 and ending with a /0/. De/ne the rev erse/-com/-plemen t of a binary v ector U /= /"/1 /"/2 /
/
/
/"l as U /?/=/"l /"l /BnZr /1 /
/
/
/"/1 /; where /" /= /1 /BnZr /" /. Then Ho/man/'s du/-alit y principle states thatH /( U /) /= H /( U /?/) /: (6–2)This relation groups the m ultiple zetas in to equalpairs and/, for instance/, implies that/ /(/2 /; /3 /; /4/) /= H /(/1/0/1/0/0/1/0/0/0/) /= H /(/1/1/1/0/1/1/0/1/0/)/= / /(/1 /; /1 /; /2 /; /1 /; /2 /; /2/) /:The pro of sk etc hed in /[Zagier /1/9/9/4/] is based onthe m ultiple in tegral represen tationH /( /"/1 /; /: /: /: /; /"k /) /= Z/
/
/
Z/0 /<t/1 /< /
/
/
/<tk /< /1 d/"/1 t/1 /
/
/
d/"k tk /;d/0 t /= dtt /; d/1 t /= dt/1 /BnZr t /;and on the c hange of v ariables uj /= /1 /BnZr tj /. W e denote b y /
the set of linear relations thatarise from dualit y /. Partial Fraction ExpansionsThe Euler/{Nielsen metho d/, of whic h an idea w asgiv en at the b eginning of Section /3/, applies to dou/-ble zetas /[Nielsen /1/9/0/6/]/, and/, as established b yMark ett /[/1/9/9/4/] and b y Borw ein and Girgensohn/[/1/9/9/6/]/, it can b e extended to triple zetas/. W e let //2and //3 denote the linear relations that arise fromthis mec hanism in the case of zetas of m ultiplicities/2 and /3/. Residue RelationsW e ha v e designed a program in system Maplethat computes relations on Euler sums that resultfrom an y k ernel that is a p olynomial form in / functions and their deriv ativ es/. W e denote b y Rthe set of relations that arise from suc h k ernels ap/-plied to /1 /=s q/; see Section /2 and the b o x on page /2/0/.Our program allo ws the exhaustiv e in v estigationof the relations deriving from the residue metho dapplied to Euler sums of a /xed giv en w eigh t/. W eha v e examined the dimension of the spaces of lin/-ear relations that result from an y com bination ofthe rules / /; /
/; //2 /; //3 /; R for all w eigh ts up to /1/0/.This can b e view ed as a supplemen t to Ho/man/'sin v estigations who obtained a complete basis of re/-lations b et w een m ultiple zetas for w eigh ts / /6/.First/, the linear relations implied b y the rules/ /; /
/; //2 /; //3 /; R tak e place a priori in the space ofpro ducts of m ultiple zetas with total w eigh t w /. Thesh u/e relations reduce these pro ducts in to linearcom binations of m ultiple zetas of w eigh t w /, form/-ing a space whose dimension is /2 w /BnZr /2/. There are Ewdistinct Euler sums/, where/1Xw /=/2 Ew z w/= z /2/1 /BnZr z /1Yj /=/1 /1/1 /BnZr z j/= z /2/+ /2 z /3/+ /4 z /4/+ /7 z /5/+ /1/2 z /6/+ /1/9 z /7/+ /3/0 z /8/+ /4/5 z /9/+ /6/7 z /1/0/+ /9/7 z /1/1/+ /
/
/
/; 30 Experimental Mathematics, Vol. 7 (1998), No. 1and standard estimates on the n um b er of partitionsimply that Ew /= e O /( pw /)/.W e seek reductions of Euler sums in to linearcom binations of monomials in single zeta v alueswhose n um b er /w satis/es/1Xw /=/0 /w z w/= /1/1 /BnZr z /2 /1Yj /=/1 /1/1 /BnZr z /2 j /+/1/= /1 /+ z /2/+ z /3/+ z /4/+ /2 z /5/+ /2 z /6/+ /3 z /7/+ /3 z /8/+ /5 z /9/+ /5 z /1/0/+ /7 z /1/1/+ /8 z /1/2/+ /
/
/
/:The gro wth order of /w is again e O /( pw /)/, thoughwith a smaller exp onen tial rate than Ew /. These/w /(presumably Q /-linearly indep enden t/) monomi/-als span the space of /\closed/-form/" expressions/.Th us/, the n um b ers of m ultiple zeta forms/, Eulersums/, and p olyzeta forms satisfy/2 w /BnZr /2/ Ew / /w /:Therefore/, one should not exp ect on these groundsall m ultiple zetas nor ev en all Euler sums to re/-duce to com binations of zeta monomials/. In otherw ords/, closed form is exc eptional for an Euler sum/.Zagier has conducted extensiv e n umerical com/-putations of m ultiple zeta v alues of all w eigh ts upto /1/2 and has examined the apparen t Q /-linear de/-p endencies that result/. Based on these compu/-tations and other algebraic argumen ts/, he conjec/-tures that the dimension dw is giv en b y the recur/-rence dw /= dw /BnZr /2 /+ dw /BnZr /3 /, d/2 /= d/3 /= d/4 /= /1/, so/1Xw /=/2 dw z w/= /1/1 /BnZr z /2/BnZr z /3/= /1 /+ z /2/+ z /3/+ z /4/+ /2 z /5/+ /2 z /6/+ /3 z /7/+ /4 z /8/+ /5 z /9/+ /7 z /1/0/+ /9 z /1/1/+ /1/2 z /1/2/+ /
/
/
/:The gro wth of dw is of the appro ximate form dw //1 /: /3/2/4/7/1 w/.Th us/, mo dulo Zagier/'s conjecture/, the dimensionof the Q /-linear space of m ultiple zeta v alues liessomewhere in b et w een the /(large/) n um b er /2 w /BnZr /2ofm ultiple zetas and the /(small/) n um b er /w of closed/- form monomials/. What is remark able/, ho w ev er/, isthat there is almost coincidence of dw and /w forw eigh ts /< /1/0/, the di/erence d/8 /BnZr //8 /= /1 b eing ac/-coun ted for b y the o ccurrence of the /(probably/)irreducible S/2 /; /6 /. Based on our program/, w e ha v ev eri/ed the reductions implied b y Zagier/'s conjec/-ture for all w eigh ts up to /9/. /(W e do not claim m uc horiginalit y for the next result/: it is largely a v eri//-cation based on tec hniques in tro duced b y Ho/man/,Zagier/, Mark ett/, Borw ein and Girgensohn/./) Theorem 6.1. A l l multiple zetas of weight / /9 ar er e ducible to Q /-line ar c ombinations of single zetamonomials with the addition of f S/2 /; /6 g for weight /8/. Proof. Solv e the linear systems deriving from thesh u/e relations //, dualit y /
/, partial fractions //2and //3 /, and residues R /. / Corollary 6.2. A l l Euler sums of the form S/1 p/;q forweights p /+ q /2 f /3 /; /4 /; /5 /; /6 /; /7 /; /9 g ar e expr essible p oly/-nomial ly in terms of zeta values /. F or weight /8/,al l such sums ar e the sum of a p olynomial in zetavalues and a r ational multiple of S/2 /; /6 /.This corollary pro vides a justi/cation of iden titiesdisco v ered exp erimen tally b y Bailey et al/. /[/1/9/9/4/]/.In passing/, the computations underlying Theo/-rem /6/./1 allo w one to delineate the p o w er of v ar/-ious reduction principles/. First/, dualit y reducesb y ab out a half the n um b er of indep enden t m ulti/-ple zetas to b e considered since it pro vides a n um/-b er /w of non trivial linear equalities that satis/es/w /= /2 w /BnZr /3when w is o dd and /w /= /2 w /BnZr /3/BnZr /2 w /= /2 /BnZr /2when w is ev en/. Next/, the sh u/e relations reduceall the pro ducts of m ultiple zetas to linear com bi/-nations of m ultiple zetas/. Besides/, the sh u/e rela/-tions induce linear relations on m ultiple zetas/. F orinstance/, since / /(/1 /; /2/) /= / /(/3/)/, the pro ducts of theseb y / /(/2/) once expanded b y the sh u/e relations yield/ /(/2 /; /1 /; /2/) /+ /2 / /(/1 /; /2 /; /2/) /+ / /(/1 /; /4/) /BnZr / /(/2 /; /3/) /BnZr / /(/5/) /= /0 /:The Nielsen relations //2 app ear to pro vide b w /= /2 cindep enden t linear relations of w eigh t w /, whic h isnot m uc h/. Also/, for o dd w eigh t/, these relationsare implied b y the residue relations R as expressed Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 31w eigh t w / /
//2 //3 R total /2 w /BnZr /2/BnZr dw/3 /0 /1 /1 /0 /1 /1 /1 /(//2 /) /; /(/
/) /; /( R /)/4 /0 /1 /2 /1 /2 /3 /3 /(//2 /; /
/) /; /(//2 /; //3 /) /; /(//2 /; R /) /; /(//3 /; R /)/5 /1 /4 /2 /3 /5 /6 /6 /(//2 /; /
/) /; /(//3 /; /
/) /; /( R /; /
/) /; /(//3 /; R /)/6 /5 /6 /3 /6 /1/0 /1/4 /1/4 /(//2 /; /
/) /; /(//3 /; /
/) /; /( R /; /
/)/7 /1/2 /1/6 /3 /1/0 /1/7 /2/9 /2/9 /(//3 /; /
/)/8 /3/1 /2/8 /4 /1/5 /3/1 /6/0 /6/0 /(//3 /; /
/) /; /( R /; /
/)/9 /6/8 /6/4 /4 /2/1 /4/5 /1/2/3 /1/2/3 /(//3 /; /
/; R /)/1/0 /1/5/1 /1/2/0 /5 /2/7 /7/5 /2/4/8 /2/4/9 /(//3 /; /
/) /; /( R /; /
/) TABLE 2. Rank of relations v ersus w eigh t/. Eac h set of relations generates a v ector space of linear relations onthe m ultiple zetas/. F or eac h w eigh t/, w e indicate the dimension of this space/, whic h giv es a measure of the p o w erof the relations/.b y Theorem /3/./1/. The Mark ett relations //3 seemto induce O /( w /2/) indep enden t linear relations ofw eigh t w /. In T able /2/, w e giv e the dimension ofthe v ector space of linear relations induced b y therule //; w e also giv e the dimension of the linearrelations induced b y //2 /, //3 /, /
/, and R once lin/-earized b y the sh u/e relations/. The total dimen/-sion of the space of relations w e get is indicated inthe next column/. It is to b e compared with thev alue /2 w /BnZr /2/BnZr dw implied b y Zagier/'s conjecture/. Inthe last column w e indicate whic h minimal com bi/-nations of relations mak e it p ossible to generate allthe kno wn relations /(in conjunction with //)/.An in teresting asp ect of the pro of of Theorem /6/./1is that residue relations con tribute new relations tothe arsenal of curren tly kno wn metho ds and p ermitto attain the limit describ ed b y Zagier/'s conjecturefor w eigh ts up to /9 inclusiv e/. This is demonstratedin the last column of T able /2/, where it app earsthat all /4 relations are necessary to get /1/2/3 in/-dep enden t linear relations of w eigh t /9 /(since thew eigh t is o dd //2 is implied b y R /)/. F or instance/,the k ernel /BnZr/ /( s /) /+ / /
/3/ /0/( /BnZr s /) applied to the basefunction /1 /=s /5induces a relation that is not a con/-sequence of the linear relations induced b y the par/-tial fraction relations together with dualit y and thesh u/e relations/. F or w eigh t /1/0/, the last line of T a/-ble /2 indicates that the relations / /; /
/; //2 /; //3 /; Rare no longer su/cien t to generate all the linearrelations implied b y Zagier/'s conjecture/. There are t w o computationally in tensiv e steps inthis v eri/cation/, the generation of all the residuerelations and the elimination pro cess/. Eliminationis required to obtain the dimension of the space ofline ar relations generated b y the nonline ar sh u/erelations/; it has b een p erformed b y a Gr/ obner basiscomputation/. 7. ALTERNATING EULER SUMSW e no w turn to the ev aluation of alternating Eulersums b y means of con tour in tegrals/. LetH /( r /)n /:/= nXj /=/1 /( /BnZr /1/) j /BnZr /1j r /; Hn /:/= H /(/1/)n /= nXj /=/1 /( /BnZr /1/) j /BnZr /1jdenote the alternating harmonic n um b ers/. Thereare altogether four t yp es of linear sums/:S /+/+p/;q /= /1Xn /=/1 H /( p /)nn q /;S /BnZr /+p/;q /= /1Xn /=/1 H /( p /)nn q /; S /+ /BnZrp/;q /= /1Xn /=/1 /( /BnZr /1/) n /BnZr /1 H /( p /)nn q /;S /BnZr/BnZrp/;q /= /1Xn /=/1 /( /BnZr /1/) n /BnZr /1 H /( p /)nn q /:Clearly the S /+/+p/;q are the standard Euler sums de/-/ned earlier/. Suc h n um b ers ha v e b een consideredb y Euler/, Nielsen and man y others/.A natural k ernel for the sums of t yp e S /+ /BnZrisa com bination of / functions and / /= sin / s /, sincethe latter in tro duces sign alternation/. Some par/-it y constrain ts m ust ho w ev er in terv ene since p oles 32 Experimental Mathematics, Vol. 7 (1998), No. 1o ccur at p ositiv e and negativ e in tegers/. The otherresults are b est stated in terms of the alternatingzeta function/,/ /( s /) /:/= /1Xn /=/1 /( /BnZr /1/) n /BnZr /1n s /= /(/1 /BnZr /2 /1 /BnZr s/) / /( s /) /;with / /(/1/) /= log /2/. Alternating harmonic n um b ersare in tro duced b y the mo di/ed / function/,// /( s /) /: /= /1Xk /=/0 /( /BnZr /1/) ks /+ k /= /1/2 / /s /+ /1/2 //BnZr /1/2 / /s/2 //= /1s /BnZr log /2 /+ / /(/2/) s /BnZr / /(/3/) s /2/+ / /(/4/) s /3/BnZr /
/
/
/:This is also kno wn as Nielsen/'s / function/; it sat/-is/es// /( n /) /= /( /BnZr /1/) n/( Hn /BnZr /1 /BnZr log /2/) /;// /( s /) /=s /!/BnZr n /( /BnZr /1/) n //1s /+ n /+ /( Hn /BnZr log /2/) /+ /
/
/
//;where n is a p ositiv e in teger/.The follo wing ev aluations are all found in /[Sitara/-mac handra Rao /1/9/8/7/]/, whic h con tains an exhaus/-tiv e discussion of sums S ///1 /;r together with a thor/-ough bibliograph y /. Here the iden tities come out assimple consequences of the pro cess emplo y ed ear/-lier for standard Euler sums/. Theorem 7.1 /[Sitaramac handra Rao /1/9/8/7/]/./(i /) F or any weight /1 /+ q /,/2 S /BnZr /+/1 /;q /= /2 / /( q /) log /2 /BnZr q / /( q /+/1/) /+ /2 / /( q /+ /1/)/+ qXk /=/1 / /( k /) / /( q /BnZr k /+ /1/) /:/(ii /) In the c ase of a weight /1 /+ q that is o dd /,/2 S /+ /BnZr/1 /;q /= /( q /+/1/) / /( q /+/1/) /BnZr / /( q /+ /1/)/BnZr /2 q /= /2 /BnZr /1Xk /=/1 / /(/2 k /) / /( q /+ /1 /BnZr /2 k /) /;/2 S /BnZr/BnZr/1 /;q /= /2/( / /( q /) /+ / /( q /)/) log /2 /BnZr /( q /+/1/) / /( q /+/1/) /+ / /( q /+/1/)/+/2 q /= /2 /BnZr /1Xk /=/1 / /(/2 k /) / /( q /+/1 /BnZr /2 k /) /:Proof. The result falls as a rip e fruit when w e useresp ectiv ely the k ernels// /( s /) /2/; /sin / s /( / /( /BnZr s /) /+ / /) /; / /( s /) / cot / s/:In the /rst case/, the sign alternation of the generalterm disapp ears b ecause of the squaring of / /( s /)/, sothat w e get directly S /BnZr /+/1 /;q /. In the other cases/, t w oalmost iden tical sums result from the residues atthe p ositiv e and negativ e in tegers/, and the com bi/-nation in v olv es a co e/cien t of /BnZr/1 /+ /( /BnZr /1/) q /
/, so thatestimates are restricted to the case of q o dd/. /Notice /nally that the use of the k ernel/ /( s /)/( / /( /BnZr s /) /+ / /)allo ws one to relate S /+ /BnZr/1 /;q and S /BnZr/BnZr/1 /;q irresp ectiv e ofthe parit y of the w eigh ts/:S /BnZr/BnZr/1 /;q /+ /( /BnZr /1/) qS /+ /BnZr/1 /;q/= / /( q /) log /2 /BnZr q /BnZr /1Xi /=/1 /( /BnZr /1/) i/ /( i /) / /( q /+ /1 /BnZr i /) /:In other w ords/, there is a new v ariet y of constan tsde/ned b y/q /= S /+ /BnZr/1 /; /2 q /+/1 /= /1Xn /=/1 /( /BnZr /1/) n /BnZr /1 Hnn /2 q /+/1 /;where/q /= /1/(/2 q /)/! Z/1/0 log /2 q/( z /) log /(/1 /+ z /)z /(/1 /+ z /) dz /:W e ha v e from /[de Do elder /1/9/9/1/; Sitaramac han/-dra Rao /1/9/8/7/]//0 /= /1/2 / /(/2/) /BnZr /1/2 log /2/2 /;//1 /= /BnZr /2 Li/4 /( /1/2 /) /+ /1/1/4 / /(/4/) /+ /1/2 / /(/2/) log /2/2/BnZr /1/1/2 log /4/2 /BnZr /7/4 / /(/3/) log /2 /;where Liq /( z /) /= P/1n /=/1 z nn /BnZr qis the p olylogarithm/.The constan t //1 is related to sev eral of Raman u/-jan/'s ev aluations as w ell as to the analysis of latticereduction /[Daud / e et al/. /1/9/9/7/] men tioned in the in/-tro duction/. Higher order / /'s are not kno wn to b erelated to classical constan ts/. Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 33Nielsen/, follo wing Euler/, pro v ed relations sug/-gesting that alternating sums of o dd w eigh t shouldreduce to p olynomials in zeta v alues augmen tedwith L /= / /(/1/) /= log /2/. This approac h is dev elop edin /[Borw ein et al/. /1/9/9/5/]/, where it is sho wn that theEuler/{Nielsen relations can b e in v erted /(though ex/-plicit form ul/ are not giv en/)/.Sh u/e relations analogous to /(/1/{ /1/)/,/ /( p /) / /( q /) /+ / /( p /+ q /) /= S /BnZr /+p/;q /+ S /+ /BnZrq /;p /;/ /( p /) / /( q /) /+ / /( p /+ q /) /= S /BnZr/BnZrp/;q /+ S /BnZr/BnZrq /;p /;reduce the n um b er of quan tities to b e in v estigated/.Ho w ev er/, since our in terest is in general summa/-tory form ul//, w e prefer to dev elop an approac hfrom scratc h/. Theorem 7.2. L et w /= p /+ q b e an o dd weight /. Then /: (i) /BnZr/( /BnZr /1/) q/BnZr /( /BnZr /1/) p /
S /BnZr /+p/;q is given by/( /BnZr /1/) p/ /( p /+ q /) /+ /(/( /BnZr /1/) p/BnZr /1/) / /( p /) / /( q /)/+ /2 Xj /+/2 k /= p /q /+ j /BnZr /1q /BnZr /1 // /( q /+ j /) / /(/2 k /)/+ /2/( /BnZr /1/) p Xi /+/2 k /= q /p /+ i /BnZr /1p /BnZr /1 //( /BnZr /1/) i/ /( p /+ i /) / /(/2 k /) /: (ii) /2 S /+ /BnZrp/;q is given by/BnZr/1 /BnZr /( /BnZr /1/) p /
/ /( p /) // /( q /) /+ // /( p /+ q /) /+ /2 Xj /+/2 k /= p /q /+ j /BnZr /1q /BnZr /1 //( /BnZr /1/) j /+/1/ /( q /+ j /) / /(/2 k /)/+ /2/( /BnZr /1/) p Xi /+/2 k /= q /p /+ i /BnZr /1p /BnZr /1 // /( p /+ i /) / /(/2 k /) /: (iii) /BnZr/( /BnZr /1/) p/BnZr /( /BnZr /1/) q /
S /BnZr/BnZrp/;q is given by/( /BnZr /1/) p /+/1/ /( p /+ q /) /+ /(/1 /BnZr /( /BnZr /1/) p/) / /( p /) / /( q /)/+ /2 Xj /+/2 k /= p /q /+ j /BnZr /1q /BnZr /1 // /( q /+ j /) / /(/2 k /)/BnZr /2/( /BnZr /1/) p Xi /+/2 k /= q /p /+ i /BnZr /1p /BnZr /1 //( /BnZr /1/) i/ /( p /+ i /) / /(/2 k /) /: Proof. Just use the k ernels /1/( p /BnZr /1/)/! / /( p /BnZr /1/)/( s /) /sin / s /,/1/( p /BnZr /1/)/! / /( p /BnZr /1/)/( s /) /sin / s /, /1/( p /BnZr /1/)/! / /( p /BnZr /1/)/( s /) / cot / s /./ 8. EXOTIC SUMSThe use of k ernels in v olving / and its relativ es isnot just restricted to Euler sums/. W e ha v e c ho/-sen here a random sample of four t yp es of /\exotic/"summatory form ul/ p oin ting the w a y to extensionsof the metho d and p ossibly to a new functional/-it y in computer algebra systems regarding sev eralclasses of in/nite summations/./( T/1 /) /2 /1Xn /=/1 /( /BnZr /1/) nr/0 /( n /) /= /BnZr R hr/0 /( s /) /sin / s i/( T/2 /) /2 /1Xn /=/1 Hn r /( n /) /BnZr /1Xn /=/1 /BnZr/2 log /2 r /( n /) /+ r /0/( n /) /
/= R // /2/( /BnZr s /) r /( s /) //( T/3 /) /2 /1Xn /=/1 /( /BnZr /1/) nHn r/0 /( n /) /+ /1Xn /=/1 /( /BnZr /1/) n /r /0/0 /( n /) /BnZr r/0 /( n /)n //= /BnZr R //( / /( /BnZr s /) /+ / /) /sin / s r/0 /( s /) //( T/4 /) /2 /1Xn /=/1 /( /BnZr /1/) nHn r/0 /( n /) /BnZr /1Xn /=/1 /( /BnZr /1/) n /BnZrr /0/0 /( n /) /+ /2 log /2 r/0 /( n /) /
/BnZr r/0 /( n /)n /= /BnZr R /BnZr/ /( s /) / cot / sr/0 /( s /) /
General summatory form ul/ for alternating sums/. Here r /( s /) /; r/0 /( s /) denote rational functions that satisfy theconditions of /(/2/{/5/)/, with additionally r/0 /( s /) ev en/. 34 Experimental Mathematics, Vol. 7 (1998), No. 1 1. Consider the family of sumsAq /:/= /1Xn /=/1 /( Hn /) /2/(/(/2 n /BnZr /1/)/(/2 n /)/(/2 n /+ /1/)/) q /:W e claim that Aq reduces to a p olynomial in zetav alues and log /2 whenev er q is o dd/.Set r /( n /) /= /BnZr/(/2 n /BnZr /1/)/(/2 n /)/(/2 n /+ /1/) /
/BnZr qand tak e qo dd/. By Equation /( S/7 /) on page /2/4/, w e ha v e a /rstreduction /(mo dulo v alues of / functions at / /1/2 /) toPHn r /0/( n /) and PH /(/2/)n r /( n /)/. The /rst sum reducesin all cases/; the second sum reduces again sincer /( s /) is assumed to b e o dd/. An instance is thenA/3 /= /BnZr/1 /
/2 /1/(/1 /2 /3/) /3 /+ /BnZr/1 /+ /1/2 /
/2 /1/(/3 /4 /5/) /3/+ /BnZr/1 /+ /1/2 /+ /1/3 /
/2 /1/(/5 /6 /7/) /3 /+ /
/
/
/= /4 ln /3/2 /+ /BnZr/7/8 / /(/3/) /BnZr /3/5/4 /
ln /2/2/BnZr /BnZr/4/5/3/2 / /(/4/)/+ /7/8 / /(/3/) /BnZr /9/8 / /(/2/) /BnZr /1/2 /
ln /2 /+ /4/5/6/4 / /(/4/)/BnZr /1/4 / /(/2/) /BnZr /3/3/2 / /(/2/) / /(/3/) /BnZr /4/1/8 / /(/3/) /+ /1/7/3/2 / /(/5/) /:Sev eral related/, but simpler/, iden tities app ear inChapter /9 of Raman ujan/'s noteb o oks/; see /[Berndt/1/9/8/9/]/. 2. Sums related to Catalan/'s constan t ha v e b eendisco v ered b y Raman ujan /[Berndt /1/9/8/9/] and fur/-ther explored b y Sitaramac handra Rao /[/1/9/8/7/]/. W eo/er here the ev aluations/1Xn /=/1 /( /BnZr /1/) n Hn/2 n /+ /1 /= /1Xn /=/0 /( /BnZr /1/) n/(/2 n /+ /1/) /2 /BnZr /1/2 / log /2 /;/1Xn /=/0 /( /BnZr /1/) n Hn/(/2 n /+ /1/) /3 /= /3 /1Xn /=/0 /( /BnZr /1/) n/(/2 n /+ /1/) /4 /BnZr /7/1/6 / / /(/3/)/BnZr /1/1/6 / /3log /2 /;and the w ell/-kno wn/1Xn /=/0 /( /BnZr /1/) n/(/2 n /+ /1/) /3 /= /1/3/2 / /3/; /1Xn /=/0 /( /BnZr /1/) n/(/2 n /+ /1/) /5 /= /5/1/5/3/6 / /5/;whic h deriv e from the k ernel /( / /( /BnZr s /) /+ / /) /sin / s /. 3. The use of k ernels in v olving i /= p/BnZr /1 in ar/-gumen ts of / functions leads to y et another class of summation form ul//. F or instance/, one has thehighly symmetrical form ulasXm/;n / /1 /1m /2/( m /2/+ n /2/) /= /1/2 / /(/2/) /2/;Xm/;n / /1 /1m /6/( m /2/+ n /2/) /= / /(/2/) / /(/6/) /BnZr /1/2 / /(/4/) /2/;Xm/;n / /1 /1mn /3/( m /2/+ n /2/) /= /1/2 / /(/3/) /2/;Xm/;n / /1 /1mn /7/( m /2/+ n /2/) /= / /(/3/) / /(/7/) /BnZr /1/2 / /(/5/) /2/(with a p erio dicit y of exp onen ts mo dulo /4/) fromthe k ernel /( / /(/1 /+ is /) /+ / /)/( / /( /BnZr s /) /+ / /)/. Zagier /[/1/9/9/4/]has studied a related but /\harder/" class of sums/. 4. Lastly /, the summation pro cess exempli/ed b ythe form ulas in the b o xes of pages /2/4 and /3/4 ex/-tends to irrational meromorphic functions pro videdthey remain small on circles /(or other large con/-tours/) on whic h the k ernel is itself small/. In thatcase/, one has a relation b et w een t w o t yp es of in//-nite sums/. F or instance/, the k ernel /( / cot / s /) ap/-plied to the functions /( / coth / s /) /=s qyields iden ti/-ties lik e/1Xn /=/1 coth / kk /3 /= /7/1/8/0 / /3/; /1Xn /=/1 coth / kk /7 /= /1/9/5/6/7/0/0 / /7whic h w ere disco v ered b y Raman ujan /[Berndt /1/9/8/5/]/. ACKNOWLEDGEMENTSEarly discussions with Brigitte V all / ee help ed clar/-ify the residue approac h to the computation ofEuler sums/. W e are grateful to Don Zagier fordetailed explanations o/ered to one of us at the/\Com binatorics and Ph ysics/" meeting at Lumin y/(Marc h /1/9/9/5/) and our curren t presen tation o w esm uc h to Zagier/'s insigh ts/. Jon Borw ein and RolandGirgensohn shared ideas/, preprin ts/, and referencesthroughout the course of this w ork/. Thanks to all/. Flajolet and Salvy: Euler Sums and Contour Integral Represe ntations 35 REFERENCES/[Bailey et al/. /1/9/9/4/] D/. H/. Bailey /, J/. M/. Borw ein/, andR/. Girgensohn/, /\Exp erimen tal ev aluation of Eulersums/"/, Exp eriment/. Math/. /3 /:/1 /(/1/9/9/4/)/, /1/7/{/3/0/./[Berndt /1/9/8/5/] B/. C/. Berndt/, R amanujan /'s noteb o oks/,II /, Springer/, New Y ork/, /1/9/8/5/. With a forew ord b y S/.Chandrasekhar/./[Berndt /1/9/8/9/] B/. C/. Berndt/, R amanujan /'s noteb o oks/, I /,Springer/, New Y ork/, /1/9/8/9/./[Borw ein and Girgensohn /1/9/9/6/] J/. M/. Borw ein andR/. Girgensohn/, /\Ev aluation of triple Euler sums/"/,Ele ctr on/. J/. Combin/. /3 /:/1 /(/1/9/9/6/)/, Researc h P ap er /2/3/,/2/7 pp/. /(electronic/)/./[Borw ein et al/. /1/9/9/5/] D/. Borw ein/, J/. M/. Borw ein/, andR/. Girgensohn/, /\Explicit ev aluation of Euler sums/"/,Pr o c/. Edinbur gh Math/. So c/. /(/2/) /3/8 /:/2 /(/1/9/9/5/)/, /2/7/7/{/2/9/4/./[Crandall and Buhler /1/9/9/4/] R/. E/. Crandall andJ/. P /. Buhler/, /\On the ev aluation of Euler sums/"/,Exp eriment/. Math/. /3 /:/4 /(/1/9/9/4/)/, /2/7/5/{/2/8/5/./[Daud / e et al/. /1/9/9/7/] H/. Daud / e/, P /. Fla jolet/, and B/. V all / ee/,/\An a v erage/-case analysis of the Gaussian algorithmfor lattice reduction/"/, Combinatorics/, Pr ob ability/,and Computing /6 /:/4 /(/1/9/9/7/)/, /3/9/7/{/4/3/3/./[de Do elder /1/9/9/1/] P /. J/. de Do elder/, /\On some seriescon taining / /( x /) /BnZr / /( y /) and /( / /( x /) /BnZr / /( y /)/) /2for certainv alues of x and y /"/, J/. Comput/. Appl/. Math/. /3/7 /:/1/-/3/(/1/9/9/1/)/, /1/2/5/{/1/4/1/./[Fla jolet et al/. /1/9/9/5/] P /. Fla jolet/, G/. Lab elle/, L/.Laforest/, and B/. Salvy /, /\Hyp ergeometrics and thecost structure of quadtrees/"/, R andom Structur esA lgorithms /7 /:/2 /(/1/9/9/5/)/, /1/1/7/{/1/4/4/. /[Henrici /1/9/7/4/] P /. Henrici/, Applie d and c omputationalc omplex analysis /, Pure and Applied Mathematics/,Wiley/-In terscience/, New Y ork/, /1/9/7/4/. Reprin ted /1/9/8/8/./[Ho/man /1/9/9/2/] M/. E/. Ho/man/, /\Multiple harmonicseries/"/, Paci/c J/. Math/. /1/5/2 /:/2 /(/1/9/9/2/)/, /2/7/5/{/2/9/0/./[Lab elle and Laforest /1/9/9/5/] G/. Lab elle and L/. Lafo/-rest/, /\Com binatorial v ariations on m ultidimensionalquadtrees/"/, J/. Combin/. The ory Ser/. A /6/9 /:/1 /(/1/9/9/5/)/,/1/{/1/6/./[Lindel/ of /1/9/0/5/] E/. Lindel/ of/, L e c alcul des r / esidus etses applic ations /a la th / eorie des fonctions /, Gauthier/-Villars/, P aris/, /1/9/0/5/. Reprin ted b y /Editions JacquesGaba y /, Sceaux/, /1/9/8/9/./[Mark ett /1/9/9/4/] C/. Mark ett/, /\T riple sums and theRiemann zeta function/"/, J/. Numb er The ory /4/8 /:/2/(/1/9/9/4/)/, /1/1/3/{/1/3/2/./[Nielsen /1/9/0/6/] N/. Nielsen/, Handbuch der The orie derGammafunktion and The orie des Inte gr al lo garithmusund verwandter Tr anszendenten /, /1/9/0/6/. Reprin tedtogether as Die Gammafunktion /, Chelsea/, New Y ork/,/1/9/6/5/./[Sitaramac handra Rao /1/9/8/7/] R/. Sitaramac handra Rao/,/\A form ula of S/. Raman ujan/"/, J/. Numb er The ory/2/5 /:/1 /(/1/9/8/7/)/, /1/{/1/9/./[Whittak er and W atson /1/9/2/7/] E/. T/. Whittak er andG/. N/. W atson/, A c ourse of mo dern analysis /, /4thed/./, Cam bridge Mathematical Library /, Cam bridgeUniv ersit y Press/, Cam bridge/, /1/9/2/7/. Reprin ted /1/9/7/3/,/1/9/9/6/./[Zagier /1/9/9/4/] D/. Zagier/, /\V alues of zeta functions andtheir applications/"/, pp/. /4/9/7/{/5/1/2 in First Eur op e anCongr ess of Mathematics /(P aris/, /1/9/9/2/)/, v ol/. I I/, editedb y A/. Joseph et al/./, Progr/. Math/. /1/2/0 /, Birkh/ auser/,Basel/, /1/9/9/4/.Philipp e Fla jolet/, Algorithms Pro ject/, INRIA/, Ro cquencourt/, F/{/7/8/1/5/3 Le Chesna y /, F rance/(Philipp e/.Fla jolet/@inria/.fr/)Bruno Salvy /, Algorithms Pro ject/, INRIA/, Ro cquencourt/, F/{/7/8/1/5/3 Le Chesna y /, F rance /(Bruno/.Salvy/@inria/.fr/)Receiv ed June /2/4/, /1/9/9/6/; accepted in revised form June /2/0/, /1/9/9/7