10.1.1.37.652

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 References Work supported in part by the Long Term Research Project Alcom-IT (# 20244) of the European 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 Euler sums in terms of Riemann zeta values. The approach is based on simple contour integral representations and residue com- putations. 1. INTRODUCTION Harmonic numbers and their generalizations are classically de�ned by H n � H (1) n := n X j=1 1 j ; H (r) n := n X j=1 1 j r : The subject of this paper is Euler sums, which are the in�nite sums whose general term is a product of harmonic numbers of index n and a power of n �1 . It has been discovered in the course of the years that many Euler sums admit expressions involving �nitely the \zeta values", that is to say values of the Riemann zeta function, �(s) := 1 X j=1 1 j s at the positive integers. Typical evaluations to be discussed here are shown at the top of the next page. Euler started this line of investigation in the course of a correspondence with Goldbach begin- ning in 1742 (see [Berndt 1989, p. 253] for a dis- cussion) and he was the �rst to consider the linear sums, S p;q := 1 X n=1 H (p) n n 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) X n�1 H n n 2 = 2�(3); X n�1 H n n 3 = 5 4 �(4); X n�1 H n n 4 = 3�(5) � �(2)�(3) (b) X n�1 H (2) n n 4 = �(3) 2 � 1 3 �(6) (c) X n�1 H (2) n n 5 = 5�(2)�(5) + 2�(3)�(4)� 10�(7) (d) X n�1 (H n ) 2 n 5 = 6�(7) � �(2)�(5)� 5 2 �(3)�(4) (e) X n�1 (H n ) 3 n 4 = 231 16 �(7)� 51 4 �(3)�(4) + 2�(2)�(5) (f) X n�1 (H n ) 4 (n+ 1) 3 = 185 8 �(7)� 43 2 �(3)�(4) + 5�(2)�(5) (g) X n�1 (H n ) 3 n 5 � 11 4 X n�1 H (2) n n 6 = 469 32 �(8)� 16�(3)�(5) + 3 2 �(2)�(3) 2 : Typical evaluations of Euler sums. Euler, whose investigations were to be later com- pleted by Nielsen [1906], discovered that the linear sums have evaluations in terms of zeta values in the following cases: p = 1; p = q; p+ q odd; p+ q even but with the pair (p; q) being restricted to a �nite set of so-called \exceptional" con�gurations f(2; 4); (4; 2)g. Of these cases, the one correspond- ing to p= q is obvious given the symmetry relations S p;q + S q;p = �(p)�(q) + �(p+ q); (1–2) while the other ones correspond to essentially non- trivial identities, of which examples (a), (b), (c) at the top of page 16 are typical. Rather extensive numerical search for linear relations between linear Euler sums and polynomials in zeta values [Bailey et al. 1994] strongly suggest that Euler found all the possible evaluations of linear sums. The next objects of interest are the nonlinear sums, involving products of at least two harmonic numbers. Let � = (� 1 ; : : : ; � k ) be a partition of integer p into k summands, so that p= � 1 +� � �+� k and � 1 � � 2 � : : : � � k . The Euler sum of index �; q is de�ned by S �;q = 1 X n=1 H (� 1 ) n H (� 2 ) n � � �H (� k ) n n q ; the quantity q+� 1 +� � �+� k being called the weight and the quantity k being the degree. As usual, repeated summands in partitions are indicated by powers, so that for instance S 1 2 2 3 5;q = S 112225;q = 1 X n=1 (H n ) 2 (H (2) n ) 3 H (5) n n q : In the past, a few basic nonlinear sums have been evaluated thanks to their relations to the Eule- rian beta integrals or to polylogarithms [de Doelder 1991]. Recently, a detailed numerical search con- ducted by Bailey, Borwein, and Girgensohn [Bailey et al. 1994] has revealed the existence of many sur- prising evaluations like examples (e) and (f) at the top of page 16. Some of these have since received Flajolet and Salvy: Euler Sums and Contour Integral Representations 17 a due proof and for instance the paper [Borwein et al. 1995] gives explicit formul� for S 1 2 ;q = 1 X n=1 (H n ) 2 n q whenever the weight q+ 2 is odd (see example (d) at the top of page 16), and an explicit reduction to S 2;q when the weight is even. The situation regarding explicit evaluations of Euler sums is at �rst sight rather puzzling. Some evaluations appear to generalize and form an in�- nite class|like S 1 2 ;q above|while others seem to vanish mysteriously as soon as the weight exceeds a certain threshold. For instance, no �nite for- mula in terms of zeta values is likely to exist for the cubic sums S 1 3 ;q or the quartic sums S 1 4 ;q of an odd weight exceeding 10, while S 1 3 ;4 ; S 1 4 ;3 (ex- amples (e) and (f) at the top of page 16) or even the septic S 1 7 ;2 do reduce to zeta values [Bailey et al. 1994]. This suggests the existence of both \general" classes of evaluations and \exceptional" evaluations. A recent approach, exempli�ed by [Ho�man 1992; Zagier 1994] sheds a new light on these phenom- ena. It is based on considering the multiple zeta functions de�ned by �(a 1 ; a 2 ; : : : ; a l ) := X n 1 n 2 > � � � > n l ; in summations. The two presentations are trivial variants of each other, obtained one from the other by changing the order of the arguments.) Every Euler sum of weight w and degree k is clearly a Q - linear combination of multiple zeta values (that is, values of multiple zeta functions at integer argu- ments) of weight w and multiplicity at most k+1. In other words, multiple zeta values are \atomic" quantities into which Euler sums decompose. Con- sequently, a complete model for the linear relations involving the multiple zeta values would yield a full decision procedure for determining whether any particular Euler sum admits a complete evaluation in terms of (single) zeta values. A conjecture of Zagier, discussed later, states that the dimension d w of the Q -linear space gener- ated by the 2 w�2 multiple zeta values of weight w increases roughly like 1:32 w . In contrast the num- ber � w of weight-homogeneous monomials in zeta values of weight w is much smaller asymptotically, being only e O( p w) . Thus, a priori, only a small fraction of quantities expressible in terms of mul- tiple zetas should reduce to polynomials in (sin- gle) zeta values. However, initially, the di�erence d w �� w is small and even equal to 0 for some of the low weights, f3; 4; 5; 6; 7; 9g. As a consequence, any Euler sum of odd weight at most 9 must reduce to zeta values. The multiple zeta model therefore ex- plains well the presence of exceptional evaluations of Euler sums that appear in this perspective to be unavoidable artefacts of low weight. A characteristic aspect of the multiple zeta model is that it may predict relations but does not in general provide explicit formul�. This is where we �t in. Our approach is based on contour integral representations. It is directed at Euler sums that are particular \nonatomic" combinations of multi- ple zeta values, having almost complete symmetry. When applicable, this approach does not require inverting collections of linear relations, which may be rather di�cult to do for a whole class of sums as exempli�ed by [Borwein et al. 1995; Borwein and Girgensohn 1996]. Euler sums and multiple zetas have connections with many branches of mathematics; see especially [Zagier 1994]. Broadhurst (see [Borwein and Gir- gensohn 1996]) encountered them in relation with Feynman diagrams and associated knots in per- turbative quantum �eld theory. They also surface occasionally in combinatorial mathematics: evalu- ation (a) at the top of page 16 serves to analyze the 18 Experimental Mathematics, Vol. 7 (1998), No. 1 distribution of node degrees in quadtrees [Flajolet et al. 1995; Labelle and Laforest 1995] while alter- nating Euler sums make an appearance in the anal- ysis of lattice reduction algorithms [Daud�e et al. 1997]. The basic techniques of this paper, beyond the Cauchy{Lindelof contour integrals of Lemma 2.1, have been worked out in an experimental manner using the computer algebra system Maple. This system \knows" the expansions of all the special functions needed here, and it has been used thor- oughly in order to extract minimal kernels and summation formul�, of which those shown in the box on page 24 are typical. Certainly, the inten- sive computations required by Section 6 (see The- orem 6.1 and Table 2) could not have been carried out manually, in view of the number of equations involved. In return, the summation formul� of this paper (like those on page 24) could very well be en- capsulated as templates in a general purpose sum- mation package. Section 8 points in this direction and lists several types of sums that can now be computed mechanically using the approach of this paper. 2. GENERAL SUMMATIONS Contour integration is a classical technique for eval- uating in�nite sums by reducing them to a �nite number of residue computations. For instance, the easy identity 2 1 X n=1 (�1) n n 2 + 1 = 2� e � � e �� � 1 can be derived transparently from a residue com- putation of the integral 1 2i� Z � sin�s ds s 2 + 1 over a circle centred at the origin and whose radius is taken arbitrarily large. The residues at the poles s = �n with n 6= 0 generate the left-hand side of the equality, while the poles at s = 0;�i yield the explicit form appearing on the right. (Of course, many other techniques can be employed to derive this identity, including Poisson's summation for- mula or Mittag-Le�er expansions of trigonometric functions.) This summation mechanism is formalized by a lemma that goes back to Cauchy and is nicely de- veloped throughout [Lindelof 1905]. We de�ne a kernel function �(s) by the two requirements: �(s) is meromorphic in the whole complex plane; �(s) satis�es �(s) = o(s) over an in�nite collection of circles jzj = � k with � k ! +1. Lemma 2.1 (Cauchy, Lindelo¨f). Let �(s) be a kernel function and let r(s) be a rational function which is O(s �2 ) at in�nity . Then X �2O Res(r(s)�(s)) s=� = � X �2S Res(r(s)�(s)) s=� (2–1) where S is the set of poles of r(s) and O is the set of poles of �(s) that are not poles of r(s). Here Res(h(s)) s=� denotes the residue of h(s) at s = �. Proof. It su�ces to apply the residue theorem to 1 2i� Z (1) r(s)�(s) ds; where R (1) denotes integration along large circles, that is, the limit of integrals R jsj=� k . See also the discussion in [Henrici 1974, x 4.9], where a kernel function is called a summatory function. � This formula does have the character of a summa- tory formula since the set O of poles of an irrational kernel �(s) (called the \ordinary poles") is in�nite, while the set S of poles of a rational function r(s) (the \special poles") is necessarily �nite. We also de�ne the special residue sum to be the �nite sum R[�(s)r(s)] := X �2S[f0g Res(�(s)r(s)) s=� : The amalgamation of 0 to the special poles is just a notational convenience dictated by the fre- Flajolet and Salvy: Euler Sums and Contour Integral Representations 19 quent need to isolate 0 in summatory formul�. Then (2{1) is rephrased as X �2Onf0g Res(r(s)�(s)) s=� = �R[�(s)r(s)]: Let [(s � �) r ]h(s) denote the coe�cient of the (s � �) r term in the Laurent expansion of h(s) at s = �. Residues are Laurent coe�cients, and as such they are computable like Taylor coe�cients, since Res(h(s)) s=� = [(s� �) �1 ]h(s) = [(s� �) r�1 ](s� �) r h(s); if r is the order of the pole of h(s) at s = �. In other words, the special residue sum is always de- termined by a few Taylor series expansions taken at a �nite collection of points. We make here an essential use of kernels involv- ing the function. The function [Whittaker and Watson 1927] is the logarithmic derivative of the Gamma function, (s) = d ds log �(s) = � � 1 s + 1 X n=1 � 1 n � 1 n+ s � (2–2) and it satis�es the complement formula (s)� (�s) = � 1 s � � cot �s; as well as an expansion at s = 0 that involves the zeta values: (s) + = � 1 s + �(2)s� �(3)s 2 + � � � : (2–3) From classical expansions and the properties just recalled of the function, one has at an integer n the expressions listed on the top of the next page. Each of these functions, or any of its derivatives, is O(jsj " ) on circles of radius n+ 1 2 (with n a positive integer) centred at the origin. Consequently, any polynomial form in � cot �s; � sin�s ; (j) (�s) (2–4) is itself a kernel function with poles at a subset of the integers. The purpose of this paper is precisely to investigate the power of such kernels in connec- tion with summatory formul� and Euler sums. We shall impose throughout two conditions on the rational function r(s): (i) r(s) is O(s �2 ) at in�nity, (ii) r(s) has no pole in Z n f0g: (2–5) Condition (i) is necessary for absolute convergence of the sums; condition (ii) is only a minor technical requirement. A direct use of the kernels of (2{4) then yields the summatory formul� 1 X n=1 r(n) = �R � r(s)( (�s) + ) � ; (2–6) 1 X n=1 (r(n) + r(�n)) = �R � r(s)� cot �s � ; (2–7) 1 X n=1 (�1) n (r(n) + r(�n)) = �R h r(s) � sin�s i ; (2–8) of which the last two are classical [Henrici 1974, x 4.9]. The kernels are (�s) + , � cot �s, and �= sin �s, as is apparent from the argument of the special residue sum. Clearly, equalities (2{7) and (2{8) become trivial if the rational function r(s) is odd, and such parity phenomena surface recur- rently in Euler sums evaluation. A more interesting kernel is ( (�s)+ ) 2 , whose residues at the positive integers generate harmonic numbers since ( (�s) + ) 2 � s!n 1 (s� n) 2 + 2H n 1 s� n + � � � : In that case, under the conditions of (2{5), we �nd 2 1 X n=1 r(n)H n + 1 X n=1 r 0 (n) = �R � r(s)( (�s) + ) 2 � ; (2–9) as results directly from the singular expansion of the kernel (see box at the top of page 20). Thus, 20 Experimental Mathematics, Vol. 7 (1998), No. 1 � cot �s = s!n 1 s� n � 2 1 X k=1 �(2k)(s� n) 2k�1 � sin�s = s!n (�1) n � 1 (s� n) + 2 1 X k=1 (1� 2 1�2k )�(2k)(s� n) 2k�1 � (�s) + = s!n 1 s� n +H n + 1 X k=1 � (�1) k H (k+1) n � �(k + 1) � (s� n) k ; if n � 0 (�s) + = s!�n H n�1 + 1 X k=1 � H (k+1) n�1 � �(k + 1) � (s+ n) k if n > 0 (p�1) (�s) (p� 1)! = s!n 1 (s� n) p � 1 + (�1) p X i�p � i� 1 p� 1 � � �(i) + (�1) i H (i) n � (s� n) i � if n � 0; p > 1 (p�1) (�s) (p� 1)! = s!�n (�1) p X i�0 � p� 1 + i p� 1 � � �(p+ i)�H (p+i) n�1 � (s+ n) i if n > 0; p > 1 1 s q = s!n X j�0 (�1) j � q + j � 1 q � 1 � (s� n) j n q+j if n 6= 0; q 2 Z + Local expansions of basic kernels. by (2{6){(2{8) and (2{9), any sum whose general term is the product of the harmonic number H n and a rational function r(n) reduces to a �nite com- bination of values of the function and its deriva- tives taken at a �nite set of points. Instantiating this treatment to the class of functions r(s) = s �q , with q an integer � 2, produces a formula already known to Euler. Theorem 2.2 (Euler). For integer q � 2, S 1;q � 1 X n=1 H n n q = (1 + q 2 )�(q + 1)� 1 2 q�2 X k=1 �(k + 1)�(q � k): Proof. A direct consequence of the summatory for- mula (2{9) and the expansion (2{3). � Special values are given in example (a) at the top of page 16. The treatment just developed of the simplest Eu- ler sums is typical. For the case when r(s) = s �q , only one residue needs to be determined, and the residue computation is strictly equivalent to a coef- �cient extraction. Given that the kernels employed throughout this paper are polynomials in and re- lated trigonometric functions, the expressions ob- tained are invariably weight-homogeneous convo- lutions of zeta values. In addition, the degree of the kernel employed (that is itself suggested by the nature of each Euler sum considered) dictates the multiplicity of the convolution formul� that are obtained by this process. Alternative Approaches Following a suggestion by a referee, we brie y dis- cuss some of the many approaches that have been developed regarding Euler sums. Partial fraction expansions of the Euler{Nielsen{Markett type (see [Nielsen 1906; Markett 1994; Borwein and Girgen- Flajolet and Salvy: Euler Sums and Contour Integral Representations 21 sohn 1996]) are instrumental is providing relations. Identities of low weight can sometimes be proved by special integral representations and functional properties of polylogarithms [de Doelder 1991]. Amongst more general methods, we mention or- thogonality and summatory formul�. A recent pa- per [Crandall and Buhler 1994] derives the linear relations of Theorems 2.2 and 3.1 using orthogonal- ity on the unit circle and the polylogarithmic series P n e 2i�nx =n � . This technique is reminiscent of the Poisson summation formula, but the extension to Euler sums of higher degree might be di�cult given the scarcity of explicit Fourier transforms involv- ing nonlinear forms in the -function. A di�erent type of orthogonality was suggested by a referee who proposed a Mellin{Perron type of formula, X n>m 1 n a m b = 1 2 �(a+ b) = 1 2i� Z c+i1 c�i1 �(a� s)�(b+ s) ds s (for some suitable c). Its possible use is however still unclear to us since the integrand has only 3 poles at s= 0, a�1, 1�b, while evaluations of Euler sums generally involve more than three terms. Our paper is on the other hand very close to the Euler{Maclaurin summation formula, especially its complex version due to Abel and Plana [Henrici 1974, p. 274]: 1 X n=0 f(n) = 1 2 f(0) + Z 1 0 f(x) dx + i Z 1 0 f(iy)� f(�iy) e 2�y � 1 dy: This formula is proved [Henrici 1974; Lindelof 1905] using the trigonometric kernel � cot �s in the style of Lemma 2.1. The goal of this paper is precisely to illustrate the versatility of nonlinear -kernels that do not seem to have surfaced in the literature despite their simplicity and their power as regards nonlinear Euler sums. An instance of this fact is the solution of the cubic conjectures of [Bailey et al. 1994] given by Corollary 5.2. Also, in Theorems 4.1 and 5.1 and in the box on page 24, such kernels are needed since purely trigonometric kernels only give access to a small subset of Euler sums, a fact con- �rmed by parity considerations as well as by the classi�cation of kernels given in Section 6. 3. LINEAR EULER SUMS Nielsen [1906], elaborating on Euler's work, proved by a method based on partial fraction expansions that every linear sum S p;q whose weight p + q is odd is expressible as a polynomial in zeta values. To give an idea of the method [Nielsen 1906, p. 50], we show that S 1;2 = 2�(3), an equality expressed in terms of double