EVALUATION OF TRIPLE EULER SUMS

Jonathan M. Borwein^{1}

CECM, Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., V5A 1S6, Canada

                  e-mail: jborwein@cecm.sfu.ca

Roland Girgensohn

Institut für Mathematik, Medizinische Universität Lübeck, D-23560 Lübeck, Germany

           e-mail: girgenso@informatik.mu-luebeck.de

Submitted: December 16, 1995; Accepted: August 7, 1996

Abstract. Let a, b, c be positive integers and define the so-called triple, double and single Euler sums by

ζ(a, b, c) := ∑_{x=1}^{∞} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} , ζ(a, b) := ∑_{x=1}^{∞} ∑_{y=1}^{x−1} \frac{1}{x^{a}y^{b}} and ζ(a) := ∑_{x=1}^{∞} \frac{1}{x^{a}} .

Extending earlier work about double sums, we prove that whenever a + b + c is even or less than 10, then ζ(a, b, c) can be expressed as a rational linear combination of products of double and single Euler sums. The proof involves finding and solving linear equations which relate the different types of sums to each other. We also sketch some applications of these results in Theoretical Physics.

Introduction

This paper is concerned with the discussion of sums of the type

ζ(a, b, c) := ∑_{x=1}^{∞} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} .

For which values of the integer parameters a, b, c can these sums be expressed in terms of the simpler series

ζ(a, b) := ∑_{x=1}^{∞} ∑_{y=1}^{x−1} \frac{1}{x^{a}y^{b}} and ζ(a) := ∑_{x=1}^{∞} \frac{1}{x^{a}}?

1Research supported by NSERC and the Shrum Endowment of Simon Fraser University. AMS (1991) subject classification: Primary 40A25, 40B05, Secondary 11M99, 33E99. Key words: Riemann zeta function, Euler sums, polylogarithms, harmonic numbers, quantum field theory, knot theory

We call sums of this type (triple, double or single) Euler sums, because Euler was the first to find relations between them (cf. [9]; of course, the single Euler sums are values of the Riemann zeta function at integer arguments).

Investigation of Euler sums has a long history. Euler’s original contribution was a method to reduce double sums to certain rational linear combinations of products of single sums. Examples for such evaluations, all due to Euler, are

ζ(2, 1) = ζ(3),
ζ(3, 1) = \frac{3}{2}ζ(4) − \frac{1}{2}ζ^{2}(2) = \frac{π^{4}}{360},
ζ(2, 2) = \frac{1}{2}ζ^{2}(2) − \frac{1}{2}ζ(4) = \frac{π^{4}}{120},
ζ(4, 1) = 2ζ(5) − ζ(2)ζ(3),
ζ(3, 2) = −\frac{11}{2}ζ(5) + 3ζ(2)ζ(3)  or
ζ(7, 4) = −\frac{331}{2}ζ(11) + 4ζ(5)ζ(6) + 21ζ(7)ζ(4) + 84ζ(9)ζ(2).

Euler proved that the double sums are reducible to single sums whenever a + b is less than 7 or when a + b is odd and less than 13. He conjectured that the double sums would be reducible whenever a + b is odd, and even gave what he hoped to be the general formula. In [4], we proved conjecture and formula (unbeknownst to us at the time, L. Tornheim had already proved reducibility, but not the formula, in [15]), and in [2], we demonstrated that it is “very likely” that double sums with a + b > 7, a + b even, are not reducible.

Euler sums have been investigated throughout this century, but usually the authors were not aware of Euler’s results, so that special instances of Euler’s identities (or identities equivalent to them) have been independently rediscovered time and again. It was mainly the publication of B. Berndt’s edition of Ramanujan’s notebooks [3] that served to fit all the scattered individual results into the framework of Euler’s work. (See the long list of references given there; a few later references can be found in [4] and in [13].)

So far, surprisingly little work has been done on triple (or higher) sums. The best results to date are due to C. Markett ([13]) and D. Barfoot/D. Broadhurst ([6]). Markett gave explicit reductions to single sums for all triple sums with a + b + c ≤ 6, and he proved an explicit formula for ζ(p, 1, 1) in terms of single sums. Barfoot and Broadhurst were led to consider Euler sums by certain ideas in quantum field theory (more on that below). Computations by Broadhurst using the linear algebra package REDUCE showed that all triple sums with a + b + c ≤ 10 or a + b + c = 12 were reducible to single and double sums. (Some earlier attempts at evaluating triple sums are due to R. Sitaramachandra Rao and M.V. Subbarao ([14]); they derived, among other things, a formula for ζ(a, a, a), see below.)

The results which we present here can be seen as an extension of Markett’s and Broadhurst’s work. We are interested in a complete analogy of Euler’s double sum results for triple sums. For what values of a + b + c is ζ(a, b, c) reducible to double and single sums? Because of the relations between the double and single sums, there can be several seemingly different evaluations of any triple Euler sum. Our main goal is therefore not so much to find the actual evaluations for the triple sums (although our methods also give us those and some are listed below), but rather to prove the following theorem.

Main Theorem. If n := a + b + c is even or less than or equal to 10, then ζ(a, b, c) can be expressed as a rational linear combination of products of single and double Euler sums of weight n.

We define the weight of a product of Euler sums as the sum of the arguments appearing in the product. For example, ζ(a)·ζ(b, c) has weight a+b+c, while ζ(n) has weight n.

Our approach to realize this goal is similar to Markett’s and Broadhurst’s (we also used it in [4] for the double sums, and it in fact goes back to Euler): we derive linear equations connecting triple sums with products of double and single sums with the same weight. These equations have integer coefficients. We then show that the equations have a unique solution in the cases stated in the theorem, where we treat the triple sums as unknowns. Thus we then know that there is an evaluation of the triple sums in terms of rational linear combinations of the products of double and single sums. We will use the following two classes of equations.

Decomposition equations:

\begin{matrix}ζ(a, b, c) + (−1)^{b−1} ∑_{j=1}^{a} A_{j}^{(a,b)}[ ∑_{i=1}^{a+b−j} A_{i}^{(a+b−j,c)}ζ(j, a + b + c − j − i, i) + \\ ∑_{i=1}^{c} B_{i}^{(a+b−j,c)}ζ(j, a + b + c − j − i, i)] \\ = (−1)^{b−1} ∑_{j=1}^{b}(−1)^{j−1}B_{j}^{(a,b)}ζ(a + b − j) · ζ(j, c), \end{matrix} (1)

where

A_{j}^{(s,t)} = \binom{s + t − j − 1}{s − j} and B_{j}^{(s,t)} = \binom{s + t − j − 1}{t − j}.

(Here and throughout this paper we set \binom{n}{k} = 0 if k < 0. This means that the identity \binom{n}{k} = \binom{n}{n−k} remains valid for all integers n ≥ 0, k ∈ ZZ.) This decomposition formula was given in a slightly more complicated form by Markett in [13]. In Theorem 1, below, we will see several other, different, decomposition formulas, but since (1) is quite accessible to our methods, we choose it as our main starting point.

Permutation equations:

ζ(a, b, c) + ζ(a, c, b) + ζ(c, a, b) = ζ(c)ζ(a, b) − ζ(a, b + c) − ζ(a + c, b). (2)

Similar permutation equations have been used in [13] and in [14]; in Theorem 2 below we give a few other such formulas.

The attentive reader may by now be dying to point out that our Euler sums will be infinite whenever a = 1, a case we have so far not excluded. In fact, we explicitly want to use these sums and the equations containing them, because the full set of equations has a much nicer structure than the subset of the equations containing sums only with finite values. We will therefore at first replace all ζ-sums by their partial sums:

ζ_{N}(a, b, c) := ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} ,

ζ_{N}(a, b) := ∑_{x=1}^{N} ∑_{y=1}^{x−1} \frac{1}{x^{a}y^{b}} and ζ_{N}(a) := ∑_{x=1}^{N} \frac{1}{x^{a}} .

We will then show that equations (1) and (2) hold with ζ replaced by ζ_{N}, and with error terms e_{N}(a, b, c) added to the right-hand sides, such that the error terms tend to 0 as N goes to infinity (in one case, e_{N} tends to a product of two zeta functions). Since we can show that the equations have a unique solution (in the unknowns ζ_{N}(a, b, c)) in the cases given in the theorem above, we can infer that ζ_{N}(a, b, c) can be written as a linear combination of products of double and single ζ_{N}-sums and error terms. Finally, we shall see that in this linear combination, the coefficients of ζ_{N}(1) and ζ_{N}(1, t) are 0 when a > 1. That means that we can take N to infinity and get ζ(a, b, c) as a linear combination of products of double and single ζ-sums. This linear combination is rational because the equations are; and its constituents have weight a + b + c, because the equations connect only quantities with the same weight.

While we were developing these methods to prove our main theorem, Philippe Flajolet and Bruno Salvy informed us about some ongoing work of theirs ([11]) to evaluate Euler sums in an entirely different way, namely using contour integration and the residue theorem. In this way they manage to prove, for example, that the sums

S(a; b, c) := ∑_{x=1}^{∞} \frac{1}{x^{a}} (∑_{y=1}^{x−1} \frac{1}{y^{b}} ) (∑_{z=1}^{x−1} \frac{1}{z^{c}} )

can be evaluated in terms of double and single sums whenever a + b + c is even. In view of Theorem 2 below, and with some work, this is equivalent to our main theorem.

We have mentioned before that in this century Euler sums have time and again attracted considerable and independent interest. There seems to be some quality to these identities that propels researchers to hunt for more and more of them once they have started the process. So it should not come as a surprise that there are applications of these identities in other fields. In fact, as noted above, Euler sums occur in perturbative quantum field theory when Feynman diagrams are evaluated in renormalized field theories; the Euler sums appear in counterterms being introduced in the process of renormalization. The fact that some Euler sums reduce to simpler sums and some do not corresponds to the structure of counterterms to be introduced. (In [8], Broadhurst and D. Kreimer identified ζ(3, 5, 3), the first irreducible triple sum, as a counterterm associated with a 7 loop diagram; this was the first time a triple sum entered quantum field theory. After seeing the results of the present paper, Broadhurst has found many more such sums as the values of Feynman diagrams.) Through the Feynman diagrams of quantum field theory there is even a “link” to knot theory: some Feynman diagrams can be associated to knots (see [12]), so that the values (Euler sums) of these Feynman diagrams are also associated to knots. All of this is currently ongoing research; the details are far from being worked out yet. An interesting result of that research could be a method to relate Euler sums directly to knots in such a way that reducible sums are associated with composite knots. However, we stress once more that all of this is very tentative at the present time; current results indicate that matters will not be so simple. (We mention that another link of Euler sums to knot invariants is sketched in [16].)

David Broadhurst has been kind enough to supply us with a short summary about the connections between Euler sums, quantum field theory and knot theory from which the preceding paragraph was condensed. We give the full text of that summary, which includes a long list of references, in Appendix 1, so that those readers interested in these connections can inform themselves directly from the experts and do not have to rely on our somewhat uninformed presentation.

Decomposition formulas

In this section we prove that equation (1) holds with ζ replaced by ζ_{N} and error terms added. We need the following lemma.

Lemma 1. Let e_{N}(a, b) := ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} \frac{1}{x^{a}y^{b}}. Then

(i) For a > 1 or b > 1, e_{N}(a, b) → 0 as N tends to infinity.

(ii) For a = b = 1, e_{N}(1, 1) = ζ_{N}(2) → ζ(2) as N tends to infinity.

Proof. (i): It suffices to consider the case a > 1, because e_{N}(a, b) = e_{N}(b, a). We have

e_{N}(a, b) ≤ e_{N}(2, 1) = ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} \frac{1}{x^{2}y}

≤ ∑_{x=1}^{N} \frac{1}{x^{2}} ∑_{y=N+1−x}^{N} \frac{1}{N + 1 − x} = ∑_{x=1}^{N} \frac{1}{x^{2}} \frac{x}{N + 1 − x}
= ∑_{x=1}^{N} (\frac{1}{x(N + 1)} + \frac{1}{(N + 1 − x)(N + 1)})
= \frac{2}{N + 1} ∑_{x=1}^{N} \frac{1}{x} → 0.

(ii): This is true because

e_{N}(1, 1) = ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} \frac{1}{xy} = ∑_{{1≤x,y≤N \atop x+y>N}} \frac{1}{xy}

and so

e_{N+1}(1, 1) − e_{N}(1, 1) = \frac{2}{N + 1} ∑_{y=1}^{N} \frac{1}{y} + \frac{1}{(N + 1)^{2}} − ∑_{x=1}^{N} \frac{1}{x(N + 1 − x)}
= \frac{1}{(N + 1)^{2}} ,

and e_{1}(1, 1) = 1. (This proof was suggested to us by the referee; it is a bit shorter than our original proof.) [figure] Now the main result in this section is the following decomposition theorem. Theorem 1. For all a, b, c, N ∈ IN the following three decomposition formulas hold. (D_{0}):

∑_{j=1}^{b} B_{j}^{(a,b)}ζ_{N}(a + b − j, j, c)

+ ∑_{j=1}^{a} A_{j}^{(a,b)} [∑_{i=1}^{j} A_{i}^{(j,c)}ζ_{N}(a + b − j, j + c − i, i) + ∑_{i=1}^{c} B_{i}^{(j,c)}ζ_{N}(a + b − j, j + c − i, i)]

= (ζ_{N}(a) · ζ_{N}(b, c) − e_{N}(a, b, c)).

(D_{1}):

ζ_{N}(a, b, c) + (−1)^{b−1} ∑_{j=1}^{a} A_{j}^{(a,b)}[ ∑_{i=1}^{a+b−j} A_{i}^{(a+b−j,c)}ζ_{N}(j, a + b + c − j − i, i) +

∑_{i=1}^{c} B_{i}^{(a+b−j,c)}ζ_{N}(j, a + b + c − j − i, i)]

= (−1)^{b−1} ∑_{j=1}^{b}(−1)^{j−1}B_{j}^{(a,b)}(ζ_{N}(a + b − j) · ζ_{N}(j, c) − e_{N}(a + b − j, j, c)).

(D_{2}):

ζ_{N}(a, b, c) + (−1)^{c−1} ∑_{j=1}^{b} A_{j}^{(b,c)}ζ_{N}(a, j, b + c − j)

+ (−1)^{c−1} ∑_{j=1}^{c} B_{j}^{(b,c)} ∑_{i=1}^{a} A_{i}^{(a,j)}ζ_{N}(i, a + j − i, b + c − j)

= (−1)^{c−1} ∑_{j=1}^{c} B_{j}^{(b,c)} ∑_{i=1}^{j}(−1)^{i−1}B_{i}^{(a,j)}(ζ_{N}(i) · ζ_{N}(a + j − i, b + c − j) − e_{N}(i, a + j − i, b + c − j)).

Here, e_{N}(a, b, c) = ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} satisfies e_{N}(a, b, c) → 0 for a + b ≥ 3 and

e_{N}(1, 1, c) → ζ(2)ζ(c), as N → ∞.

Proof. First of all, we note that

ζ_{N}(a) · ζ_{N}(b, c) = (∑_{x=1}^{N} \frac{1}{x^{a}} ) · (∑_{y=1}^{N} ∑_{z=1}^{y−1} \frac{1}{y^{b}z^{c}} )
= ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{(x − y)^{a}y^{b}z^{c}} + ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}}
= ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{(x − y)^{a}y^{b}z^{c}} + e_{N}(a, b, c).

We will also need the well-known formulas (cf. [4] or [13] or even [9])

\frac{1}{k^{s}(n − k)^{t}} = ∑_{j=1}^{s} \frac{A_{j}^{(s,t)}}{n^{s+t−j}k^{j}} + ∑_{j=1}^{t} \frac{B_{j}^{(s,t)}}{n^{s+t−j}(n − k)^{j}}

and

\frac{1}{k^{s}(k − n)^{t}} = (−1)^{t} ∑_{j=1}^{s} \frac{A_{j}^{(s,t)}}{n^{s+t−j}k^{j}} + (−1)^{t} ∑_{j=1}^{t} \frac{B_{j}^{(s,t)}(−1)^{j}}{n^{s+t−j}(k − n)^{j}} ,

which are of course equivalent. Now we can prove the three decomposition formulas. (D_{0}):

ζ_{N}(a) · ζ_{N}(b, c) − e_{N}(a, b, c) =

= ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{(x − y)^{a}y^{b}z^{c}}

= ∑_{x=1}^{N} ∑_{y=1}^{x−1} [∑_{j=1}^{b} \frac{A_{j}^{(b,a)}}{x^{a+b−j}y^{j}} + ∑_{j=1}^{a} \frac{B_{j}^{(b,a)}}{x^{a+b−j}(x − y)^{j}} ] ∑_{z=1}^{y−1} \frac{1}{z^{c}}

= ∑_{j=1}^{b} B_{j}^{(a,b)}ζ_{N}(a + b − j, j, c) + ∑_{j=1}^{a} A_{j}^{(a,b)}ζ̃_{N}(a + b − j, j, c),

where

ζ̃_{N}(s, t, u) := ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{s}(x − y)^{t}z^{u}} = ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{x−y−1} \frac{1}{x^{s}y^{t}z^{u}}

= ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=y+1}^{x−1} \frac{1}{x^{s}y^{t}(z − y)^{u}} = ∑_{x=1}^{N} ∑_{z=1}^{x−1} ∑_{y=1}^{z−1} \frac{1}{x^{s}y^{t}(z − y)^{u}}

= ∑_{x=1}^{N} ∑_{z=1}^{x−1} ∑_{y=1}^{z−1} \frac{1}{x^{s}} [∑_{i=1}^{t} \frac{A_{i}^{(t,u)}}{y^{i}z^{u+t−i}} + ∑_{i=1}^{u} \frac{B_{i}^{(t,u)}}{(z − y)^{i}z^{u+t−i}} ]

= ∑_{i=1}^{t} A_{i}^{(t,u)}ζ_{N}(s, u + t − i, i) + ∑_{i=1}^{u} B_{i}^{(t,u)}ζ_{N}(s, u + t − i, i).

(D_{1}): Here we follow Markett’s proof, with the difference that we consider the finite sums ζ_{N} where Markett used the infinite sums ζ.

ζ_{N}(a, b, c) = ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} = ∑_{x=1}^{N} ∑_{y=1}^{x−1} \frac{1}{x^{a}(x − y)^{b}} ∑_{z=1}^{x−y−1} \frac{1}{z^{c}}

= ∑_{x=1}^{N} ∑_{y=1}^{x−1} [(−1)^{b} ∑_{j=1}^{a} \frac{A_{j}^{(a,b)}}{y^{a+b−j}x^{j}} + (−1)^{b} ∑_{j=1}^{b} \frac{B_{j}^{(a,b)}(−1)^{j}}{y^{a+b−j}(x − y)^{j}} ] ∑_{z=1}^{x−y−1} \frac{1}{z^{c}}

= (−1)^{b} ∑_{j=1}^{a} A_{j}^{(a,b)}ζ̃(j, a + b − j, c)

+ (−1)^{b} ∑_{j=1}^{b}(−1)^{j}B_{j}^{(a,b)} ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{(x − y)^{a+b−j}y^{j}z^{c}}

= (−1)^{b} ∑_{j=1}^{a} A_{j}^{(a,b)}ζ̃(j, a + b − j, c)

+ (−1)^{b} ∑_{j=1}^{b}(−1)^{j}B_{j}^{(a,b)}(ζ_{N}(a + b − j)ζ_{N}(j, c) − e_{N}(a + b − j, j, c)),

where ζ̃(s, t, u) is the same as above.

(D_{2}):

ζ_{N}(a, b, c) = ∑_{z=1}^{N} ∑_{y=1}^{x−1} ∑_{z−1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}} = ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{y^{b}(y − z)^{c}}

= ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} [(−1)^{c} ∑_{j=1}^{b} \frac{A_{j}^{(b,c)}}{z^{b+c−j}y^{j}} + (−1)^{c} ∑_{j=1}^{b} \frac{B_{j}^{(b,c)}(−1)^{j}}{z^{b+c−j}(y − z)^{j}} ]

= (−1)^{c} ∑_{j=1}^{b} A_{j}^{(b,c)}ζ_{N}(a, j, b + c − j) + (−1)^{c} ∑_{j=1}^{c}(−1)^{j}B_{j}^{(b,c)} ζ^{≈}_{N}(a, j, b + c − j),

where

ζ^{≈}_{N}(s, t, u) := ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{y−1} \frac{1}{x^{s}(y − z)^{t}z^{u}} = ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=1}^{x−y−1} \frac{1}{x^{s}(x − y − z)^{t}z^{u}}

= ∑_{x=1}^{N} ∑_{y=1}^{x−1} ∑_{z=y+1}^{x−1} \frac{1}{x^{s}(x − z)^{t}(z − y)^{u}} = ∑_{x=1}^{N} ∑_{z=1}^{x−1} ∑_{y=1}^{z−1} \frac{1}{x^{s}(x − z)^{t}(z − y)^{u}}

= ∑_{x=1}^{N} ∑_{z=1}^{x−1} ∑_{y=1}^{z−1} \frac{1}{x^{s}(x − z)^{t}y^{u}}

= ∑_{x=1}^{N} ∑_{z=1}^{x−1} [(−1)^{t} ∑_{i=1}^{s} \frac{A_{i}^{(s,t)}}{z^{s+t−i}x^{i}} + (−1)^{t} ∑_{i=1}^{t} \frac{B_{i}^{(s,t)}(−1)^{i}}{z^{s+t−i}(x − z)^{i}} ] ∑_{y=1}^{z−1} \frac{1}{y^{u}}

= (−1)^{t} ∑_{i=1}^{s} A_{i}^{(s,t)}ζ_{N}(i, s + t − i, u) + (−1)^{t} ∑_{i=1}^{t}(−1)^{i}B_{i}^{(s,t)}ζ_{N}(i)ζ_{N}(s + t − i, u).

Finally, to prove the assertion about the behaviour of the error terms we need Lemma 1. For a > 1 and b = 1 we have

e_{N}(a, 1, c) = ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{y−1} \frac{1}{x^{a}yz^{c}} ≤ ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{N} \frac{1}{x^{a}yz^{c}}
= ζ_{N}(c) · e_{N}(a, 1) ≤ ζ_{N}(1)^{2} · \frac{2}{N + 1}

by the proof of Lemma 1(i); the last expression tends to 0. The proof for a = 1 and b > 1 is similar. Finally, for a = b = 1 we have

e_{N}(1, 1, c) − ζ_{N}(c)e_{N}(1, 1) = ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{y−1} \frac{1}{xyz^{c}} − ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=1}^{N} \frac{1}{xyz^{c}}

= ∑_{x=1}^{N} ∑_{y=N+1−x}^{N} ∑_{z=y}^{N} \frac{1}{xyz^{c}} = ∑_{x=1}^{N} ∑_{z=N+1−x}^{N} ∑_{y=N+1−z}^{N} \frac{1}{xyz^{c}}

≤ ∑_{x=1}^{N} ∑_{z=1}^{N} ∑_{y=N+1−z}^{N} \frac{1}{xyz^{c}} = ζ_{N}(1) · e_{N}(c, 1),

which tends to 0 as before if c > 1. [figure]

As mentioned in the introduction, we will need only Markett’s decomposition formula (D_{1}). It would also be possible to use (D_{0}) or (D_{2}) as the starting point. In fact, we first proved our main theorem with the use of (D_{0}). The first step in our proof was to reduce the equations (D_{0}) to another set of equations which we thought had a structure better suited to our purposes. Only later did we realize that the reduced equations were just Markett’s (D_{1}). We then also checked (D_{2}) and found that it is about as easy (or difficult) to use as (D_{1}).

All three sets of equations are in fact equivalent: each can be expressed as a linear combination of the other two. We chose to give all three equations and their proofs here because we wanted to clarify the different possibilities for decomposing the triple sums. This may be also be of interest when attempting to treat quadruple or higher sums.

Permutation formulas

Let

S_{N}(a; b, c) := ∑_{x=1}^{N} \frac{1}{x^{a}} (∑_{y=1}^{x−1} \frac{1}{y^{b}} ) (∑_{z=1}^{x−1} \frac{1}{z^{c}} ) .

We now formulate four identities between sums of the type ζ_{N} and sums of the type S_{N}. From these the formula (2) with ζ replaced by ζ_{N} can be derived, as well as some other permutation formulas. (We call them permutation formulas because they give relations between different zeta sums with certain permutations of the arguments).

Theorem 2. For any a, b, c, N ∈ IN we have

(i) S_{N}(a; b, c) = ζ_{N}(a, b, c) + ζ_{N}(a, c, b) + ζ_{N}(a, b + c),
(ii) S_{N}(a; b, c) = ζ_{N}(c)ζ_{N}(a, b) − ζ_{N}(c, a, b) − ζ_{N}(a + c, b),
(iii) S_{N}(a; b, c) = ζ_{N}(b)ζ_{N}(a, c) − ζ_{N}(b, a, c) − ζ_{N}(a + b, c),
(iv) S_{N}(a; b, c) = ζ_{N}(b, c, a) + ζ_{N}(c, b, a) − ζ_{N}(c)ζ_{N}(b, a) + ζ_{N}(b)ζ_{N}(a, c)
− ζ_{N}(a + b, c) + ζ_{N}(b, a + c) + ζ_{N}(b + c, a).

(Note that there are no error terms involved.) the electronic journal of combinatorics 3 (1996), #R23 11 Proof. (i):

S_{N}(a; b, c) = ∑_{x=1}^{N} \frac{1}{x^{a}} (∑_{y=1}^{x−1} \frac{1}{y^{b}} ) (∑_{z=1}^{x−1} \frac{1}{z^{c}} )
= ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{y=1}^{x−1} \frac{1}{y^{b}} ∑_{z=1}^{y−1} \frac{1}{z^{c}} + ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{y=1}^{x−1} \frac{1}{y^{b+c}} + ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{y=1}^{x−1} \frac{1}{y^{b}} ∑_{z=y+1}^{x−1} \frac{1}{z^{c}}
= ζ_{N}(a, b, c) + ζ_{N}(a, b + c) + ∑_{x=1}^{N} \frac{1}{x^{a}} ∑_{z=1}^{x−1} \frac{1}{z^{c}} ∑_{y=1}^{z−1} \frac{1}{y^{b}}
= ζ_{N}(a, b, c) + ζ_{N}(a, b + c) + ζ_{N}(a, c, b).

(ii),(iii):

ζ_{N}(a, b, c) = ∑_{N>x>y>z>0} \frac{1}{x^{a}y^{b}z^{c}} = ∑_{z=1}^{N} ∑_{y=z+1}^{N} ∑_{x=y+1}^{N} \frac{1}{x^{a}y^{b}z^{c}}
= ∑_{y=1}^{N} ∑_{z=1}^{y−1} ∑_{x=y+1}^{N} \frac{1}{x^{a}y^{b}z^{c}}
= ∑_{y=1}^{N} ∑_{z=1}^{y−1} ∑_{x=1}^{N} \frac{1}{x^{a}y^{b}z^{c}} − ∑_{y=1}^{N} ∑_{z=1}^{y−1} \frac{1}{y^{a+b}z^{c}} − ∑_{y=1}^{N} ∑_{z=1}^{y−1} ∑_{x=1}^{y−1} \frac{1}{x^{a}y^{b}z^{c}}
= ζ_{N}(a)ζ_{N}(b, c) − ζ_{N}(a + b, c) − S_{N}(b; a, c),

from which (ii) and (iii) follow. (iv):

ζ_{N}(a, b, c) = ∑_{z=1}^{N} ∑_{y=z+1}^{N} ∑_{x=y+1}^{N} \frac{1}{x^{a}y^{b}z^{c}}
= ∑_{z=1}^{N} ∑_{y=z+1}^{N} ∑_{x=y}^{N} \frac{1}{x^{a}y^{b}z^{c}} − ∑_{z=1}^{N} ∑_{y=z+1}^{N} \frac{1}{y^{a+b}z^{c}}
= ∑_{z=1}^{N} ∑_{x=z+1}^{N} ∑_{y=z+1}^{x} \frac{1}{x^{a}y^{b}z^{c}} − ζ_{N}(a + b, c)
= ∑_{z=1}^{N} ∑_{x=z+1}^{N} ∑_{y=1}^{N} \frac{1}{x^{a}y^{b}z^{c}} − ∑_{z=1}^{N} ∑_{x=z+1}^{N} ∑_{y=1}^{z−1} \frac{1}{x^{a}y^{b}z^{c}} − ∑_{z=1}^{N} ∑_{x=z+1}^{N} \frac{1}{x^{a}z^{b+c}}

− ∑_{z=1}^{N} ∑_{x=z+1}^{N} ∑_{y=x+1}^{N} \frac{1}{x^{a}y^{b}z^{c}} − ζ_{N}(a + b, c)

= ζ_{N}(b)ζ_{N}(a, c) − ∑_{z=1}^{N} ∑_{x=1}^{N} ∑_{y=1}^{z−1} \frac{1}{x^{a}y^{b}z^{c}} + ∑_{z=1}^{N} ∑_{x=1}^{z−1} ∑_{y=1}^{z−1} \frac{1}{x^{a}y^{b}z^{c}} + ∑_{z=1}^{N} ∑_{y=1}^{z−1} \frac{1}{y^{b}z^{a+c}}
− ζ_{N}(a, b + c) − ζ_{N}(b, a, c) − ζ_{N}(a + b, c)
= ζ_{N}(b)ζ_{N}(a, c) − ζ_{N}(a)ζ_{N}(c, b) + S_{N}(c; a, b) + ζ_{N}(a + c, b)
− ζ_{N}(a, b + c) − ζ_{N}(b, a, c) − ζ_{N}(a + b, c),

from which (iv) follows. [figure]

Identity (2) now follows by setting equal identities (i) and (ii) in Theorem 2. We have stated identities (iii) and (iv) purely for the sake of completeness; they are not needed in what follows.

We shall, however, need the following double sum permutation formula (cf. [9] or [4], there called reflection formula):

ζ_{N}(a, b) + ζ_{N}(b, a) = ζ_{N}(a)ζ_{N}(b) − ζ_{N}(a + b).  (3)

The corresponding matrices

Note that the decomposition as well as the permutation formulas relate only triple sums with the same weight to each other; in other words, their arguments satisfy a+b+c = n, where n is a (given) constant. For each n ∈ IN, therefore, we get a system of linear equations for the \frac{1}{2}(n − 1)(n − 2) unknowns ζ_{N}(1, n − 2, 1), ζ_{N}(2, n − 3, 1), …, ζ_{N}(n − 2, 1, 1), ζ_{N}(1, n−3, 2), …, ζ_{N}(n−3, 1, 2), …, ζ_{N}(1, 1, n−2). The number of equations is twice the number of unknowns, because the number of decomposition and permutation equations is \frac{1}{2}(n − 1)(n − 2) each.

In order to investigate solvability of the equations we consider the (\frac{1}{2}(n − 1)(n − 2)

× \frac{1}{2}(n − 1)(n − 2))-matrices which are connected to the decomposition formulas and to the permutation formulas separately.

Let k, l ∈ \{1, 2, …, \frac{1}{2}(n − 1)(n − 2)\}. Define

s ∈ {1, 2, …, n − 2} and u ∈ {1, …, n − s − 1} by k = ∑_{j=1}^{s−1}(n − j − 1) + u

and

t ∈ {1, 2, …, n − 2} and v ∈ {1, …, n − t − 1} by l = ∑_{j=1}^{t−1}(n − j − 1) + v.

(One should convince oneself that these numbers are indeed uniquely determined by the equations.)

Then the permutation matrix P (n), corresponding to the equations (2) with ζ replaced by ζ_{N}, is of the form

P (n) = Id + P_{1} + P_{2}

with

P_{k,l}^{(1)} = \{ \begin{matrix}1 & if v = u and t = n − s − u, \\ 0 & else, \end{matrix} P_{k,l}^{(2)} = \{ \begin{matrix}1 & if v = s and t = n − s − u, \\ 0 & else. \end{matrix}

The decomposition matrix M(n), corresponding to the set of equations (D_{1}), is of a similar form:

M(n) = Id + M_{1} + M_{2}

with

(M_{1})_{k,l} = (−1)^{n−u−s−1}\binom{n − v − t − 1}{s − t}\binom{n − v − s − 1}{u − v},

(M_{2})_{k,l} = (−1)^{n−u−s−1}\binom{n − v − t − 1}{s − 1}\binom{n − v − s − 1}{u − v}.

Our aim is to show that the decomposition and the permutation equations together determine the unknowns uniquely if n is even. This would be proved if we could show that

M(n) · x = 0 and P (n) · x = 0 implies x = 0  (4)

for all \frac{1}{2}(n − 1)(n − 2)-vectors x if n is even.

The structure of the matrices M(n) and P (n)

Our main reason for using the decomposition equatios (D_{1}) is that its corresponding matrix M(n) and the matrix P (n) have a similar structure. It is possible to show that

M_{1}^{2} = M_{2}^{3} = (M_{1}M_{2})^{2} = (M_{2}M_{1})^{2} = Id

and

P_{1}^{2} = P_{2}^{3} = (P_{1}P_{2})^{2} = (P_{2}P_{1})^{2} = Id,

but we will only need a subset of these identities.

Lemma 2. The following matrix identities hold.

(i) P_{1}^{2} = Id, (ii) (P_{2}P_{1})^{2} = Id, (iii) P_{2}^{2} = P_{1}P_{2}P_{1}.

Proof. These identities are easy to see if one interpretes P_{1}, P_{2} as permutation matrices and looks at which rows or columns they permute. Here is a more formal proof anyway:

(i):

(P_{1}^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1} δ_{i,u}δ_{j,n−s−u} · δ_{i,v}δ_{t,n−j−i} = δ_{u,v} ∑_{j=1}^{n−2} δ_{j,n−s−u}δ_{t,n−j−u} = δ_{u,v}δ_{s,t}.

(ii): We have

\begin{aligned}(P_{2}P_{1})_{k,l} & = & ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1} δ_{i,s}δ_{j,n−s−u} · δ_{i,v}δ_{t,n−j−i} \\ & = & δ_{s,v} ∑_{j=1}^{n−2} δ_{j,n−s−u}δ_{t,n−j−s} = δ_{s,v}δ_{t,u}, \end{aligned}  (5)

and thus

((P_{2}P_{1})^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1} δ_{s,i}δ_{j,u}δ_{j,v}δ_{t,i} = δ_{s,t}δ_{u,v}.

(iii):

(P_{1} · (P_{2}P_{1}))_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1} δ_{i,u}δ_{j,n−s−u} · δ_{j,v}δ_{t,i} = δ_{u,t}δ_{v,n−s−u}

and

(P_{2}^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1} δ_{i,s}δ_{j,n−s−u} · δ_{j,v}δ_{t,n−i−j}

= δ_{v,n−s−u} ∑_{i=1}^{s+u−1} δ_{i,s}δ_{t,s+u−i} = δ_{t,u}δ_{v,n−s−u}.

[figure]

These identities imply that P_{2}^{3} = P_{2} · P_{1}P_{2}P_{1} = Id and that (P_{1}P_{2})^{2} = P_{1}P_{2}P_{1} · P_{2} = P_{2}^{2} · P_{2} = Id.

Finally: The proof that the equations have a unique solution for even n

Our goal is to show that condition (4) is satisfied; this entails analyzing the conditions M(n) · x = 0 and P (n) · x = 0. It is actually possible to show that

M(n) · x = 0 ⟺ M_{2}M_{1} x = x and (Id + M_{2} + M_{2}^{2}) x = 0,

P (n) · x = 0 ⟺ P_{2}P_{1} x = x and (Id + P_{2} + P_{2}^{2}) x = 0,

but we need only the following.

Lemma 3. If P (n) · x = 0 then P_{2}P_{1} x = x.

Proof. Assume P (n) · x = 0. Using the matrix identities (Lemma 2), this implies P_{2}^{2}P (n)·x = (P_{2}^{2}+P_{2}^{2}P_{1}+Id) x = (P_{1}P_{2}P_{1}+P_{1}P_{2}+P_{1}P_{1}) x = 0. Since P_{1} is invertible, we get (P_{2}P_{1} + P_{2} + P_{1}) x = 0. Together with P (n) · x = (Id + P_{1} + P_{2}) x = 0, this implies P_{2}P_{1} x = x. [figure]

Our goal (4) is now proved if we can show that

P_{2}P_{1} x = x and (Id + M_{1} + M_{2}) x = 0 implies x = 0.  (6)

Let N_{1} := M_{1}P_{2}P_{1}, N_{2} := M_{2}P_{2}P_{1} and N := Id + N_{1} + N_{2}. Then (6) in turn is a consequence of

N x = 0 implies x = 0.

In other words, we have to show that N is invertible for n even. We will prove below (Lemma 4) that N_{1}^{2} = (N_{2}N_{1})^{2} = Id and N_{1}N_{2}N_{1} = (−1)^{n+1}N_{2}^{2}. This implies (N_{1}N_{2})^{2} = Id, N_{2}^{3} = (−1)^{n+1}Id and N_{2}N_{1}N_{2} = N_{1}. Now with these identities it is easy to show that N satisfies (N^{2}−Id)(N −2Id) = 0 if n is even and N(N −Id)(N −3Id) = 0 if n is odd. This nicely distinguishes the cases and shows N is invertible for n even.

The above matrix identities for N_{1}, N_{2} remain to be shown. Using formula (5), we find that

(N_{1})_{k,l} = (−1)^{n−u−s−1}\binom{n − t − v − 1}{s − v}\binom{n − t − s − 1}{u − t},

(N_{2})_{k,l} = (−1)^{n−u−s−1}\binom{n − t − v − 1}{s − 1}\binom{n − t − s − 1}{u − t}.

To evaluate products involving these matrices we employ the following well-known identity for binomial coefficients: For non-negative integers m, ν, μ ∈ IN_{0} we have

∑_{i=1}^{m}(−1)^{i−1}\binom{m − i}{ν}\binom{μ}{i − 1} = \binom{m − μ − 1}{m − ν − 1}.  (7)

We used this identity in [4] to evaluate double Euler sums, but for the sake of completeness we sketch a Proof. We use the generating functions

∑_{m=1}^{∞}(−1)^{m−1}\binom{μ}{m − 1}x^{m} = x · (1 − x)^{μ} for μ = 0, 1, 2, …,

∑_{m=0}^{∞} \binom{m}{ν}x^{m} = x^{ν} · \frac{1}{(1 − x)^{ν+1}} for ν = 0, 1, 2, …,

∑_{m=0}^{∞} \binom{m + k − 1}{m}x^{m} = \frac{1}{(1 − x)^{k}} for k ∈ ZZ.  (8)

(The last generating function might be in doubt for negative k, but here we can use

∑_{m=0}^{∞}(−1)^{m}\binom{−k}{m}x^{m} = (1 − x)^{−k} for k ≤ 0,

after observing that

(−1)^{m}\binom{−k}{m} = (−1)^{m} \frac{(−k) · (−k − 1) · . . . · (−k − m + 1)}{m · (m − 1) · . . . · 1}
= \frac{m + k − 1) · (m + k − 2) · . . . · (k + 1) · k}{m · (m − 1) · . . . · 1}
= \binom{m + k − 1}{m}.)

Now multiplying the first two generating functions and using the Cauchy product gives the left-hand side of (7), and expanding x^{ν+1}/(1−x)^{ν+1−μ} via (8) gives the right-hand side of (7). [figure]

After setting μ = m − 1 in (7) and doing an index transformation we get: For integers m, k, ν ≥ 0 we have

∑_{i=1}^{m+k−1}(−1)^{i−1}\binom{m + k − i − 1}{ν}\binom{m − 1}{i − k} = (−1)^{k−1}\binom{0}{m − ν − 1}.  (9)

With this identity we can now establish the final lemma.

Lemma 4. (i) N_{1}^{2} = Id, (ii) (N_{2}N_{1})^{2} = Id, (iii) N_{1}N_{2}N_{1} = (−1)^{n+1}N_{2}^{2}.

Proof. (i): We use identity (9) first with m = n − j − t, k = t, ν = n − s − j − 1 and then with m = n − t − v, k = v, ν = n − u − s − 1.

(N_{1}^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1}(−1)^{n−s−u−1}\binom{n − i − j − 1}{s − i}\binom{n − j − s − 1}{u − j} ·

· (−1)^{n−i−j−1}\binom{n − t − v − 1}{j − v}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{min\{u,n−t−1\}}(−1)^{s−u−j−1}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{n − t − j − 1} ·

· ∑_{i=1}^{n−j−1}(−1)^{i−1}\binom{n − i − j − 1}{n − s − j − 1}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{min\{u,n−t−1\}}(−1)^{s−u−j−t}\binom{n − j − s − 1}{n − u − s − 1}\binom{n − t − v − 1}{j − v}\binom{0}{s − t}

= δ_{s,t}(−1)^{u−1} ∑_{j=1}^{n−t−1}(−1)^{j−1}\binom{n − j − t − 1}{n − u − s − 1}\binom{n − s − v − 1}{j − v}

= δ_{s,t}(−1)^{u−v}\binom{0}{u + s − t − v} = δ_{s,t}δ_{u,v}.

(ii): We first prove that

(N_{2}N_{1})_{k,l} = (−1)^{n−u}\binom{t − 1}{n − u − s − 1}\binom{n − t − v − 1}{s − 1},  (10)

using identity (9) with m = n − j − t, k = t, ν = s − 1:

(N_{2}N_{1})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1}(−1)^{n−u−s−1}\binom{n − i − j − 1}{s − 1}\binom{n − j − s − 1}{u − j} ·

· (−1)^{n−i−j−1}\binom{n − t − v − 1}{j − v}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{n−t−1}(−1)^{s−u−j−1}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{n − t − j − 1} ·

· ∑_{i=1}^{n−j−1}(−1)^{i−1}\binom{n − i − j − 1}{s − 1}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{n−t−1}(−1)^{s−u−j−t}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{j − v}\binom{0}{n − j − t − s}

= (−1)^{n−u}\binom{t − 1}{u − n + t + s}\binom{n − t − v − 1}{n − t − v − s}.

To prove the assertion we now use identity (9) with m = t, k = n − t − j, ν = s − 1 and with m = n − t − v, k = 1, ν = n − u − s − 1:

((N_{2}N_{1})^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1}(−1)^{n−u}\binom{j − 1}{n − u − s − 1}\binom{n − i − j − 1}{s − 1} ·

· (−1)^{n−i}\binom{t − 1}{n − i − j − 1}\binom{n − t − v − 1}{j − 1}

= ∑_{j=1}^{n−t−v}(−1)^{u−1}\binom{j − 1}{n − u − s − 1}\binom{n − t − v − 1}{n − t − v − j} ·

· ∑_{i=1}^{n−j−1}(−1)^{i−1}\binom{n − i − j − 1}{s − 1}\binom{t − 1}{i + t + j − n}

= ∑_{j=1}^{n−t−v}(−1)^{n−u−j−t}\binom{j − 1}{n − u − s − 1}\binom{n − t − v − 1}{n − t − v − j}\binom{0}{t − s}

= δ_{t,s} ∑_{j=1}^{n−t−v}(−1)^{v−u+j−1}\binom{n − t − v − j}{n − u − s − 1}\binom{n − t − v − 1}{j − 1}

= (−1)^{v−u}δ_{t,s}\binom{0}{u + s − t − v} = δ_{t,s}δ_{u,v}.

(iii): To prove the following evaluation of N_{1}N_{2}N_{1} we use representation (10) and identity (9) with m = t, k = n − j − t, ν = n − j − s − 1:

(N_{1} · (N_{2}N_{1}))_{k,l} =

= ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1}(−1)^{n−u−s−1}\binom{n − i − j − 1}{s − i}\binom{n − j − s − 1}{u − j} ·

· (−1)^{n−i}\binom{t − 1}{n − i − j − 1}\binom{n − t − v − 1}{j − 1}

= ∑_{j=1}^{min\{u,n−t−v\}}(−1)^{u−s}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{n − t − v − j} ·

· ∑_{i=1}^{n−j−1}(−1)^{i−1}\binom{n − i − j − 1}{n − s − j − 1}\binom{t − 1}{i + t + j − n}

= ∑_{j=1}^{min\{u,n−t−v\}}(−1)^{n−j−t−u−s−1}\binom{n − j − s − 1}{n − u − s − 1}\binom{n − t − v − 1}{j − 1}\binom{0}{t − n + s + j}

= (−1)^{u−1}\binom{t − 1}{n − u − s − 1}\binom{n − t − v − 1}{n − t − s − 1}.

Now compare this with the following evaluation of N_{2}^{2}, where we again use identity (9), now with m = n − j − t, k = t, ν = s − 1:

(N_{2}^{2})_{k,l} = ∑_{j=1}^{n−2} ∑_{i=1}^{n−j−1}(−1)^{n−u−s−1}\binom{n − i − j − 1}{s − 1}\binom{n − j − s − 1}{u − j} ·

· (−1)^{n−i−j−1}\binom{n − t − v − 1}{j − 1}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{n−t−v}(−1)^{u−s−j−1}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{n − t − v − j} ·

· ∑_{i=1}^{n−j−1}(−1)^{i−1}\binom{n − i − j − 1}{s − 1}\binom{n − t − j − 1}{i − t}

= ∑_{j=1}^{n−t−v}(−1)^{u−s−j−t}\binom{n − j − s − 1}{u − j}\binom{n − t − v − 1}{j − 1}\binom{0}{n − j − t − s}

= (−1)^{n−u}\binom{t − 1}{n − u − s − 1}\binom{n − t − v − 1}{n − t − s − 1}.

[figure]

Why does this prove the main theorem?

Assume that there is some ζ_{N}(a, b, c) of weight n := a + b + c which is uniquely determined by the equations. (We have just seen that this is true, for example, whenever n is even.) This means that ζ_{N}(a, b, c) can be written as a rational linear combination of what appears on the right-hand sides of the equations, namely terms of the form ζ_{N}(s) · ζ_{N}(t, u) − e_{N}(s, t, u) and ζ_{N}(u)ζ_{N}(s, t) − ζ_{N}(s, t + u) − ζ_{N}(s + u, t) where s + t + u = n. In principle, we could now let N tend to infinity, and conclude that ζ(a, b, c) can be evaluated as a rational linear combination of the limits of the above terms, which are products of double and single zeta sums of weight n. There is a problem, however: the above terms include sums of the form ζ_{N}(1, …) which are unbounded when N tends to infinity. Such sums can (and will) appear in the evaluation of the (bounded) sum ζ_{N}(a, b, c) with a > 1. The combination of these sums in the evaluation of ζ_{N}(a, b, c) must tend to a finite limit (because ζ_{N}(a, b, c) does), but we still have to show that this limit is a combination of bounded zeta sums.

For this purpose, we have to take a closer look at the unbounded terms which can occur, and then apply the double-sum permutation formula (3) to them. The terms in question are

ζ_{N}(1)ζ_{N}(s, t)  with s > 1,
ζ_{N}(s)ζ_{N}(1, t) = ζ_{N}(s) · (−ζ_{N}(t, 1) + ζ_{N}(1)ζ_{N}(t) − ζ_{N}(t + 1)) with s, t > 1,
ζ_{N}(1)ζ_{N}(1, s) = ζ_{N}(1) · (−ζ_{N}(s, 1) + ζ_{N}(1)ζ_{N}(s) − ζ_{N}(s + 1)) with s > 1,
ζ_{N}(s)ζ_{N}(1, 1) = ζ_{N}(s) · (\frac{1}{2}ζ_{N}(1)^{2} − \frac{1}{2}ζ_{N}(2)) with s > 1 and
ζ_{N}(1, s) = −ζ_{N}(s, 1) + ζ_{N}(1)ζ_{N}(s) − ζ_{N}(s + 1) with s > 1.

All of these terms can appear, multiplied by some rational factors not depending on N, in the evaluation of ζ_{N}(a, b, c). Now we collect terms. Then we get

ζ_{N}(a, b, c) = r_{0}(N) + r_{1}(N) · ζ_{N}(1) + r_{2}(N) · ζ_{N}(1)^{2},  (11)

where r_{0}(N), r_{1}(N) and r_{2}(N) are rational linear combinations of products of bounded single and double ζ_{N}-sums, and error terms. (The products in r_{0}(N) have weight a + b+c, those in r_{1}(N) have weight a+b+c−1, and those in r_{2}(N) have weight a+b+c−2.) Now divide equation (11) by ζ_{N}(1)^{2} and let N tend to infinity. Then r_{2}(N) must tend to 0, because the other terms all do. This information can now be used to show that in fact r_{2}(N) · ζ_{N}(1)^{2} tends to 0. Remember that ζ_{N}(1)^{2} = O(ln(N)^{2}). Now, each of the terms in r_{2}(N) tends to a finite limit; the products of single and double ζ_{N}-sums converge with order at most O(1/N), while we have seen in the proof of Theorem 1 that the error terms e_{N}(a, b, c) converge with order at most O(ln(N)^{2}/N). Therefore, r_{2}(N) is of order at most O(ln(N)^{2}/N), and so r_{2}(N) · ζ_{N}(1)^{2} indeed converges to 0.

Knowing this, we can divide equation (11) by ζ_{N}(1) and repeat the above argument to get that also r_{1}(N) · ζ_{N}(1) tends to 0 with N to infinity.

Now we get the following evaluation for ζ(a, b, c):

ζ(a, b, c) = lim_{N→∞} ζ_{N}(a, b, c) = lim_{N→∞}(r_{0}(N) + r_{1}(N) · ζ_{N}(1) + r_{2}(N) · ζ_{N}(1)^{2}) = r_{0},

where r_{0} = lim_{N→∞} r_{0}(N) is a rational linear combination of products of single and double zeta sums, as asserted.

As mentioned above, all of this proves the first part of our main theorem: When a + b + c is even, then ζ_{N}(a, b, c) is uniquely determined by the equations, and so ζ(a, b, c) is evaluable by double and single zeta sums. But what happens in the case where a + b + c is odd? It is easy to check computationally (for instance using Maple or Mathematica) that the decomposition and permutation equations together have a unique solution whenever a + b + c ≤ 10. Therefore, the above arguments apply in this case and show the second part of our main theorem.

This leaves the case a + b + c ≥ 11, odd. This case is not included in our theorem, and in fact we strongly suspect that these sums can not be evaluated in terms of simpler sums. What happens here on the surface is that the equations do not have a unique solution. In fact, experimentally, the deficiencies of the full equation system (which includes all of the permutation equations) are

1, 2, 2, 4, 5, 6, 8, 10, 11, 14, 16, 18,

for odd weights beginning at 11. This sequence seems to be given by ⌈k^{2}/12⌉ − 1 with n = 2k+3 as the weight. Symbolic computation shows that the adjunction of ζ(5, 3, 3) suffices to determine all solutions of weight 11. Similarly, ζ(7, 3, 3) and ζ(5, 5, 3) suffice for weight 13; ζ(9, 3, 3) and ζ(7, 5, 3) suffice for weight 15; while ζ(11, 3, 3), ζ(9, 5, 3), ζ(7, 7, 3) and ζ(7, 5, 5) suffice for weight 17.

The suggestion to choose these sums as the base out of the many possible ones one could choose is due to Broadhurst. More generally, he conjectures that the set

{ζ(2a + 1, 2b + 1, 2c + 1) | a ≥ b ≥ c > 0, a > c}

constitutes a base for the irreducible Euler sums of weight n = 2(a + b + c) + 3. (This would neatly explain the ⌈k^{2}/12⌉ − 1 formula.) Although there are strong physical arguments for the belief that these values are indeed independent over I Q, a watertight proof appears to be difficult. Thus, it is desirable to at least subject these values to further tests with D.H. Bailey’s and H.R.P. Ferguson’s Integer Relation Detection Algorithm (cf. [2], [1] or [10]) to check independence, and this has been done for the most part in [7] and [5].

Some explicit evaluations and concluding remarks

We have used our equation system to obtain explicit evaluations for all sums with (even and odd) weights ≤ 16. Our results mesh for weights ≤ 12 with those of David Broadhurst and for weights ≤ 6 with those of Markett. Here are a few explicit evaluations; some of them were given previously by Markett and Broadhurst.

ζ(2, 1, 1) = ζ(4),
ζ(2, 1, 2) = \frac{9}{2} ζ(5) − 2 ζ(3)ζ(2),
ζ(2, 2, 1) = −\frac{11}{2} ζ(5) + 3 ζ(3)ζ(2),
ζ(3, 1, 1) = 2 ζ(5) − ζ(3)ζ(2),
ζ(4, 1, 1) = \frac{23}{16} ζ(6) − ζ(3)^{2},
ζ(2, 1, 3) = ζ(3)^{2} − \frac{13}{16} ζ(6),
ζ(3, 2, 1) = 3 ζ(3)^{2} − \frac{203}{48} ζ(6),
ζ(2, 2, 2) = \frac{3}{16} ζ(6),
ζ(3, 1, 2) = \frac{53}{24} ζ(6) − \frac{3}{2} ζ(3)^{2},
ζ(2, 3, 1) = \frac{53}{24} ζ(6) − \frac{3}{2} ζ(3)^{2},
ζ(3, 3, 1) = −\frac{9}{2} ζ(5)ζ(2) + \frac{61}{8} ζ(7),
ζ(5, 1, 1) = −\frac{5}{4} ζ(3)ζ(4) + 5 ζ(7) − 2 ζ(5)ζ(2),
ζ(3, 2, 2) = \frac{9}{4} ζ(3)ζ(4) + \frac{157}{16} ζ(7) − \frac{15}{2} ζ(5)ζ(2),
ζ(4, 1, 2) = \frac{5}{8} ζ(7) + \frac{5}{2} ζ(5)ζ(2) − \frac{15}{4} ζ(3)ζ(4),
ζ(4, 2, 1) = \frac{7}{2} ζ(3)ζ(4) − \frac{221}{16} ζ(7) + \frac{11}{2} ζ(5)ζ(2),

ζ(2, 1, 4) = \frac{7}{4} ζ(3)ζ(4) + \frac{61}{8} ζ(7) − \frac{11}{2} ζ(5)ζ(2),
ζ(2, 4, 1) = −\frac{5}{4} ζ(3)ζ(4) − \frac{109}{16} ζ(7) + 5 ζ(5)ζ(2),
ζ(3, 1, 3) = \frac{1}{4}ζ(3)ζ(4) − \frac{1}{4} ζ(7),
ζ(2, 2, 3) = −\frac{3}{2} ζ(3)ζ(4) − \frac{291}{16} ζ(7) + 12 ζ(5)ζ(2),
ζ(2, 3, 2) = \frac{75}{8} ζ(7) − \frac{11}{2} ζ(5)ζ(2).

All of these evaluations were obtained by choosing a regular subset of our equations and solving it. This gave us the triple sums in terms of single and double sums. Then we reduced the double sums to single sums with the formulas from [4], and then we further simplified the obtained formulas by making use of the relations between zeta function values at even arguments. Since every double sum of weight less or equal to 7 is reducible to single sums, the first triple sums which are not reducible to a linear combination of single sums alone occur at weight 8, and none can occur at weight 9. Here are a few examples of higher weight evaluations:

ζ(5, 1, 2) = \frac{157}{360} ζ(8) − \frac{3}{2} ζ(3)^{2}ζ(2) + \frac{2}{5} ζ(5, 3) + \frac{5}{2} ζ(3)ζ(5),
ζ(5, 2, 2) = \frac{2513}{72} ζ(9) − \frac{8}{3} ζ(3)ζ(6) + \frac{2}{3} ζ(3)^{3} + \frac{7}{4} ζ(5)ζ(4) − 21 ζ(7)ζ(2),
ζ(4, 5, 1) = 2 ζ(7, 3) + ζ(5)^{2} − 17 ζ(3)ζ(7) + ζ(2)ζ(5, 3) + 10 ζ(2)ζ(3)ζ(5) − \frac{21}{20} ζ(10),
ζ(6, 1, 4) = \frac{4}{5} ζ(5, 3, 3) − \frac{109}{12} ζ(6)ζ(5) − \frac{2561}{30} ζ(11) − \frac{38}{15} ζ(3)ζ(8) + ζ(5)ζ(3)^{2}

− \frac{2}{5} ζ(3)ζ(5, 3) + 57 ζ(9)ζ(2) + \frac{12}{5} ζ(7)ζ(4),

ζ(7, 3, 2) = −\frac{1259899}{33168} ζ(12) + 14 ζ(2)ζ(3)ζ(7) + 8 ζ(3)ζ(5)ζ(4) − 2 ζ(9, 3)

+ 44 ζ(5)ζ(7) + 4 ζ(2)ζ(7, 3) + 4 ζ(4)ζ(5, 3) − 37 ζ(3)ζ(9) − 3 ζ(2)ζ(5)^{2} + 2 ζ(3)^{2}ζ(6).

Note that at weight 11, the first irreducible triple sums occur. Following Broadhurst’s suggestion, we chose ζ(5, 3, 3) as the first basis element.

Significantly, even in the case of odd weights greater than 10, some of the triple sums are uniquely determined by the equations and are therefore evaluable in terms of products of double and single sums. They are ζ(2, 5, 4), ζ(4, 5, 2) and ζ(9, 1, 1) for weight 11, ζ(11, 1, 1) for weight 13, and ζ(5, 4, 6), ζ(5, 5, 5), ζ(6, 4, 5) and ζ(13, 1, 1) for weight 15. Some of these are easily explained: That the sums of the form ζ(n − 2, 1, 1) can be evaluated for every n follows from Markett’s results in [13] and also from our results in [4]; in fact, in both papers an explicit formula for these sums is proved. Moreover, any sum of the form ζ(a, a, a) can be directly evaluated from the permutation formulas alone; with the use of Theorem 2 and the two-dimensional reflection formula (3) it is easy to see that

ζ(a, a, a) = \frac{1}{6}ζ(a)^{3} − \frac{1}{2}ζ(a)ζ(2a) + \frac{1}{3}ζ(3a).

(This formula was also given by R. Sitaramachandra Rao and M.V. Subbarao in [14].)

Additionally, Theorem 2 and our previous results on double sums allow for the evaluation of many S(a; b, c).

While we have provided conventional proofs of the main theorem, our path to knowledge was somewhat less conventional. We were led to consider which triple sums were evaluable after seeing David Broadhurst’s extensive symbolic and numerical computations. Having finally come upon the precise equation system we exploit, we first verified – in part in Maple and in part in Mathematica – that the “infinities” (sums of the form ζ(1, …)) caused no practical problem. The way we actually handle the infinities here represents our third and most satisfactory approach. Finally, we were directed to a proof of the non-singularity of our system for even weights by (i) checking the system was invertible for even n < 40 and then (ii) by experimenting with various ways of decomposing the matrix M(n). We must have checked hundreds of matrix decompositions and identities before we finally saw the sequence of lemmata which we used here to establish non-singularity of the equations.

All of this settles the question which triple sums are reducible. But we cannot yet claim to have a lot of insight into the structures occuring here. Why are some of these sums reducible by our method, and some are not? And what can be said about quadruple or higher sums? Do they exhibit a similar structure?

We now close this paper with two conjectures.

Conjecture 1 (Broadhurst). Every double sum can be expressed by single sums plus double sums of the form

B_{2} := {ζ(2a + 1, 2b + 1) | a ≥ 2b > 0}.

Likewise, the sums of the form

B_{3} := {ζ(2a + 1, 2b + 1, 2c + 1) | a ≥ b ≥ c > 0, a > c}

constitute, together with the single and double sums, a base for the triple sums.

Broadhurst has verified that these triple sums do form a base for weights up to 35.

Conjecture 2. Consider the k-fold sums

ζ(a_{1}, a_{2}, …, a_{k}) := ∑_{x_{1}>x_{2}>...>x_{k}>0} \frac{1}{x_{1}^{a_{1}} · x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}} .

Then ζ(a_{1}, …, a_{k}) evaluates in terms of lower sums whenever a_{1} + … + a_{k} and k are of different parity. Moreover, there exists a strictly increasing sequence of integers w_{2} < w_{3} < … such that all ζ(a_{1}, …, a_{k})’s of weight less than or equal to w_{k} are reducible.

We have seen that it is very likely that w_{2} = 7 and w_{3} = 10. Broadhurst expected, arguing via knot theory, that w_{4} = 15. However, we later learned that Don Zagier had numerical evidence that quadruple sums of weight 12 would already be irreducible, so that w_{4} = 11. This seeming contradiction was then resolved by Broadhurst’s discovery that quadruple sums of weight 12 can in fact be reduced to simpler sums if one admits alternating sums as well; see [7]. It in fact appears now that the whole universe of non-alternating plus alternating sums is much better behaved than the world of the non-alternating sums alone. This is somehat substantiated by recent work in [5].

How should one go about handling quadruple and higher sums? It is entirely possible that a straight-forward generalization of the methods presented here leads to a treatment of the general case. However, the equations and matrices one would have to handle there will be very unwieldy – perhaps to the point of exhaustion or total obscurity. A different approach is needed here; but we hope to have intrigued and excited the reader enough to convince him or her that this is a subject well worth further pursuit.

References

[1] D.H. Bailey and H.R.P. Ferguson, Numerical results on relations between numerical constants using a new algorithm, Math. Comp. 53 (1989), 649–656.

[2] D.H. Bailey, J.M. Borwein and R. Girgensohn, Experimental evaluation of Euler sums, Experimental Math. 3 (1994), 17–30.

[3] B.C. Berndt, “Ramanujan’s notebooks,” Part I (Springer-Verlag, New York 1985).

[4] D. Borwein, J.M. Borwein and R. Girgensohn, Explicit evaluation of Euler sums, Proc. Edinburgh Math. Soc. 38 (1995), 277–294.

[5] J.M. Borwein, D.M. Bradley and D.J. Broadhurst, “Evaluations of k−fold Euler/Zagier sums: a compendium of results for arbitrary k,” June 1996. [CECM Research Report 96:067]

[6] D.T. Barfoot and D.J. Broadhurst, Z_{2} × S_{6} symmetry of the two-loop diagram, Zeitschrift für Physik C41 (1985), 599–606.

[7] D.J.Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, Open University preprint OUT–4102–62.

[8] D.J. Broadhurst and D. Kreimer, Knots and numbers in ϕ^{4} theory to 7 loops and beyond, International Journal of Modern Physics C6 (1995), 519–524.

[9] L. Euler, Meditationes circa singulare serierum genus, Novi Comm. Acad. Sci. Petropol. 20 (1775), 140–186. Reprinted in “Opera Omnia”, Ser. 1, Vol. XV (Teubner, Berlin 1917), 217–267.

[10] H.R.P. Ferguson and D.H. Bailey, A polynomial time, numerically stable integer relation algorithm, RNR Technical Report RNR-91-032, NASA Ames Research Center, MS T045-1, Moffett Field, CA 94035-1000.

[11] P. Flajolet and B. Salvy, Euler sums and contour integral representations, preprint

[12] D. Kreimer, Knots and divergences, Physics Letters B354 (1995), 117–124.

[13] C. Markett, Triple sums and the Riemann zeta function, J. Number Theory 48 (1994), 113–132.

[14] R. Sitaramachandra Rao and M.V. Subbarao, Transformation formulae for multiple series, Pacific J. Math. 113 (1984), 471–479.

[15] L. Tornheim, Harmonic double series, Amer. J. Math. 72 (1950), 303–314.

[16] D. Zagier, Values of zeta functions and their generalizations, in: A. Joseph et al., ed.: Proceedings of the First European Congress of Mathematics, Paris, vol. II, Birkhäuser Verlag 1994 (Progress in Mathematics, vol. 120), pp. 497–512.

APPENDIX 1: Euler sums in quantum field theory

D.J. Broadhurst, Physics Department, Open University, Milton Keynes MK7 6AA, UK.

Single Euler sums, starting with ζ(3), have long been known to occur in perturbative quantum field theory (pQFT), where physical quantities are expanded in powers of a renormalized coupling constant, after the subtraction of infinities from the corresponding Feynman diagrams. Indeed it is possible to find classes of Feynman diagrams that generate the entire sequence of terms ζ(2n + 1) [A1] and to sum such series [A6].

The first appearance of a irreducible double sum in pQFT was recorded in [A2]. It is now known [A10] that this can be expressed in terms of ζ(5, 3) and occurs in the renormalization of the simplest field theory – ϕ^{4}-theory – at the 6-loop level.

Triple sums were encountered in [A3], where it was necessary to evaluate a large number of terms of the form ζ(a, b, c) with a + b + c ≤ 9, all of which proved to be reducible. At this time, Broadhurst investigated all such triple sums with a+b+c ≤ 12 and obtained, by methods similar to (but less systematic than) those presented here, explicit reduction to a basis comprising products of single sums, ζ(5, 3), ζ(7, 3), and a single irreducible triple sum: ζ(3, 5, 3), in complete accord with the present findings.

Subsequently, there has been progress in understanding which transcendentals occur in the various calculations of pQFT [A5, A7]. At low energies, where masses are important, there is a wide variety of polylogarithmic functions that may occur, such as Li_{4}(\frac{1}{2}) [A4], which lies outside the class of sums considered here. But from massless Feynman diagrams one is much more likely to generate Euler sums in the course of computing the perturbation expansion.

Most significant, from the point of view of the present analysis, is the recent connection [A8, A9] between knot theory and the counterterms that are introduced in the process of renormalizing a quantum field theory. It is a prediction of this approach that one will encounter transcendentals in counterterms that are in correspondence with positive prime knots that result from applying the skein relation (now viewed as a renormalization procedure) to link diagrams that encode the intertwining of loop momenta in Feynman diagrams. This sets a premium on knowing which Euler sums are irreducible, since a minimal basis of these should correspond to positive knots more complex than the torus knots (2L − 3, 2) associated with the appearance of ζ(2L − 3) in L-loop counterterms. In general, positive knots with up to 2L − 3 crossings result from L-loop diagrams, though special circumstances, such as the existence of local gauge symmetry [A11] may result in cancellations.

Recent investigations [A10, A12] have confirmed that the knots 8_{19} and 10_{124} correspond to the appearance of ζ(5, 3) and ζ(7, 3) in counterterms. Moreover there are only two positive prime knots with 11 crossings: one is associated with ζ(11), the other with ζ(3, 5, 3). The confirmation given here that the deficiency of triple sums with weight 11 is indeed 1 is thus in intriguing agreement with the connection between knot theory, field theory, and number theory. Clearly work needs to be done to investigate the possibility of a direct connection between number theory and knot theory, independently of the field theory that suggests it. In the meantime, the new data furnished here by the deficiency value 2, for triple sums of weight 13, informs field theory [A12].

References

[A1] D J Broadhurst, ‘Evaluation of a class of Feynman diagrams for all numbers of loops and dimensions’, Physics Letters B164 (1985) 356-360.

[A2] D J Broadhurst, ‘Exploiting the 1,440-fold symmetry of the master two-loop diagram’, Zeitschrift für Physik C32 (1986) 249-253.

[A3] D T Barfoot and D J Broadhurst, ‘Z_{2} × S_{6} symmetry of the two-loop diagram’, Zeitschrift für Physik C41 (1988) 81-85.

[A4] D J Broadhurst, ‘Three-loop on-shell charge renormalization without integration: Λ\overline{MS} QED to four loops’, Zeitschrift für Physik C54 (1992) 599-606.

[A5] D J Broadhurst, ‘Which Feynman diagrams are algebraically computable?,’ New Computing Techniques in Physics Research II, ed. D Perret-Gallix (World Scientific, 1992) 579-584.

[A6] D J Broadhurst, ‘Summation of an infinite series of ladder diagrams’, Physics Letters B307 (1993) 132-139.

[A7] D J Broadhurst, ‘Progress with multi-loop diagrams since AI-92,’ New Computing Techniques in Physics Research III, ed. K-H Becks and D Perret-Gallix (World Scientific, Singapore, 1994) 511-516.

[A8] D Kreimer, Renormalization and Knot Theory, UTAS-PHYS-94-25, to appear in Journal of Knot Theory and its Ramifications.

[A9] D Kreimer, ‘Knots and divergences’, Physics Letters B354 (1995) 117-124.

[A10] D J Broadhurst and D Kreimer, ‘Knots and numbers in ϕ^{4} theory to 7 loops and beyond’, International Journal of Modern Physics C6 (1995) 519-524.

[A11] D J Broadhurst, R Delbourgo and D Kreimer, ‘Unknotting the polarized vacuum of quenched QED’, OUT–4102–60 (September 1995), to appear in Physics Letters B. (hep-ph/9509296)

[A12] D J Broadhurst, J A Gracey and D Kreimer, ‘Beyond the triangle and uniqueness relations: non-zeta counterterms at large N from positive knots,’ OUT– 4102–46 (December 1995).