GENERATING FUNCTIONS AND

GENERALIZED DEDEKIND SUMS

Ira M. Gessel

Department of Mathematics Brandeis University Waltham, MA 02254-9110 gessel@math.brandeis.edu

Submitted: August 31, 1996; Accepted: October 1, 1996

Dedicated to Herb Wilf, in honor of his 65th birthday

Abstract. We study sums of the form ∑_{ζ} R(ζ), where R is a rational function and the sum is over all nth roots of unity ζ (often with ζ = 1 excluded). We call these generalized Dedekind sums, since the most well-known sums of this form are Dedekind sums. We discuss three methods for evaluating such sums: The method of factorization applies if we have an explicit formula for ∏_{ζ}(1 − xR(ζ)). Multisection can be used to evaluate some simple, but important sums. Finally, the method of partial fractions reduces the evaluation of arbitrary generalized Dedekind sums to those of a very simple form.

1. Introduction.

Given a rational function R(x), we consider the problem of evaluating the sum

∑_{ζ} R(ζ)

over all nth roots of unity ζ (often with ζ = 1 excluded.) Such problems arise in several areas of mathematics, such as number theory and topology, and this work was originally motivated by a question from Larry Smith [9] regarding sums of this form that arose in his work on stable homotopy theory [8].

Although there is a large literature on special instances of such sums, there does not seem to have been any discussion of the general problem. Since the special cases that have been studied are usually called Dedekind sums, we call the sums considered here generalized Dedekind sums. For a comprehensive account of the classical theory of Dedekind sums, see Rademacher and Grosswald [7]. An elegant treatment of an important generalization of the classical Dedekind sum has been given by Zagier [11].

1991 Mathematics Subject Classification. Primary 11F20, Secondary 05A15.

This work is partially supported by NSF grant DMS-9622456.

In this paper we discuss three methods, all using generating functions, for studying such sums. The first method is factorization: If we have an “explicit” formula for the product P (x) = ∏_{j}(1 − α_{j}x), then we can use it to study the sums ∑_{j} α_{j}^{k}. We apply this in the case in which α_{j} is R(ζ_{j}) for some rational function R, where ζ_{j} is an nth root of unity.

The second method is multisection: If R(x) = ∑_{k} r_{k}x^{k} then ∑_{ζ^{n}=1} R(ζx) = n ∑_{k} r_{nk}x^{nk}. If R is rational and we have an explicit formula for ∑_{k} r_{nk}x^{nk}, then we have evaluated ∑_{ζ^{n}=1} R(ζx), and we can set x = 1 (sometimes after subtracting the ζ = 1 term) to evaluate ∑_{ζ^{n}=1} R(ζ) or ∑_{{ζ^{n}=1 \atop ζ≠1}} R(ζ).

The third, and most powerful, method is partial fractions: Since any rational function is a linear combination of rational functions of the form (x − α)^{−i}, the general problem may be reduced to the case of this particular form, which can be solved by either of the first two methods or by a further application of partial fractions. Partial fractions can also be used to derive “reciprocity theorems” which are important in the theory of classical Dedekind sums.

2. Factorization.

Let P (x) be a polynomial and suppose that

P (x) = ∏_{j}(1 − α_{j}x).

Then

− log P (x) = ∑_{k=1}^{∞}(∑_{j} α_{j}^{k})\frac{x^{k}}{k} .  (2.1)

Thus if for some rational function R, α_{j} is R(ζ_{j}), where ζ_{j} is a root of unity, and if we know P (x) explicitly, then we have a generating function for ∑_{j} R(ζ_{j})^{k}.

The simplest interesting example comes from

z^{n} − 1 = ∏_{ζ^{n}=1}(z − ζ).  (2.2)

Setting z = x + α in (2.2) gives

(x + α)^{n} − 1 = ∏_{ζ^{n}=1}(x − (ζ − α)).

Dividing each side by its constant term we get

\frac{(α + x)^{n} − 1}{α^{n} − 1} = ∏_{ζ^{n}=1} (1 − \frac{x}{ζ − α}) .

the electronic journal of combinatorics 4 (no. 2) (1997), #R11 3

Then applying (2.1), we have

log \frac{α^{n} − 1}{(α + x)^{n} − 1} = ∑_{k=1}^{∞}( ∑_{ζ^{n}=1} \frac{1}{(ζ − α)^{k}} )\frac{x^{k}}{k} .  (2.3)

Extracting the coefficients of x and x^{2} in (2.3) gives

∑_{ζ^{n}=1} \frac{1}{ζ − α} = −n\frac{α^{n−1}}{α^{n} − 1}  (2.4)
∑_{ζ^{n}=1} \frac{1}{(ζ − α)^{2}} = n\frac{α^{n−2}(α^{n} + n − 1)}{(α^{n} − 1)^{2}}.  (2.5)

Similarly, we may start from

\frac{z^{n} − 1}{z − 1} = ∏_{{ζ^{n}=1 \atop ζ≠1}}(z − ζ).  (2.6)

Setting z = x + 1 in (2.6) gives

\frac{(1 + x)^{n} − 1}{x} = ∏_{{ζ^{n}=1 \atop ζ≠1}}(x − (ζ − 1)).

Dividing each side by its constant term we get

\frac{(1 + x)^{n} − 1}{nx} = ∏_{{ζ^{n}=1 \atop ζ≠1}} (1 − \frac{x}{ζ − 1}) .

Now let

g_{k}(n) = ∑_{{ζ^{n}=1 \atop ζ≠1}}(ζ − 1)^{−k}.

Using the facts that if ζ = e^{2πij/n}, where i = \sqrt{−1}, then

\frac{1}{(ζ − 1)^{k}} = \frac{ζ^{−k/2}}{(ζ^{1/2} − ζ^{−1/2})^{k}} = (\frac{1}{2i})^{k} \frac{cos \frac{πjk}{n} − i sin \frac{πjk}{n}}{sin^{k} \frac{πj}{n}} ,

and that g_{k}(n) is real, we obtain trigonometric formulas for g_{k}(n): If k is even,

g_{k}(n) = \frac{(−1)^{k/2}}{2^{k}} ∑_{j=1}^{n−1} cos \frac{πjk}{n} csc^{k} \frac{πj}{n} ,

and if k is odd,

g_{k}(n) = \frac{(−1)^{(k−1)/2}}{2^{k}} ∑_{j=1}^{n−1} sin \frac{πjk}{n} csc^{k} \frac{πj}{n} .

By (2.1),

∑_{k=1}^{∞} g_{k}(n)\frac{x^{k}}{k} = log \frac{nx}{(1 + x)^{n} − 1}.  (2.7)

From (2.7), we can easily compute the first few values of g_{k}(n):

g_{1}(n) = −(n − 1)/2
g_{2}(n) = −(n − 1)(n − 5)/12,
g_{3}(n) = (n − 1)(n − 3)/8.
g_{4}(n) = (n − 1)(n^{3} + n^{2} − 109n + 251)/720
g_{5}(n) = −(n − 1)(n − 5)(n^{2} + 6n − 19)/288
g_{6}(n) = −(n − 1)(2n^{5} + 2n^{4} − 355n^{3} − 355n^{2} + 11153n − 19087)/60480

The problem of showing that g_{k}(n) = ∑_{{ζ^{n}=1 \atop ζ≠1}} (ζ − 1)^{−k} is a polynomial in n of degree at most k with rational coefficients was proposed by Duran [5]. This result follows easily from (2.7), but we can say much more about these polynomials.

First we recall that the unsigned Stirling numbers of the first kind \left[{n \atop k}\right] are defined by

\frac{(log(1 + x))^{k}}{k!} = ∑_{n=k}^{∞}(−1)^{n−k}\left[{n \atop k}\right]\frac{x^{n}}{n!}

and the Bernoulli numbers B_{n} are defined by

\frac{x}{e^{x} − 1} = ∑_{n=0}^{∞} B_{n} \frac{x^{n}}{n!} .

It is well known that B_{1} = −1/2, and for n > 1 B_{n} is zero if and only if n is odd.

Theorem 2.1. For k ≥ 1,

g_{k}(n) = (−1)^{k} \frac{n − 1}{2} − \frac{1}{(k − 1)!} ∑_{j=2}^{k}(−1)^{k−j}\left[{k \atop j}\right]\frac{B_{j}}{j} (n^{j} − 1).

Proof. Let us set x = e^{y} − 1, so that y = log(1 + x). Then by (2.7),

∑_{k=1}^{∞} g_{k}(n)\frac{x^{k}}{k} = − log \frac{e^{ny} − 1}{n(e^{y} − 1)} = log \frac{ny}{e^{ny} − 1} − log \frac{y}{e^{y} − 1}.

Since

\frac{d}{du} log \frac{u}{e^{u} − 1} = \frac{1}{u} (−\frac{u}{e^{u} − 1} + 1 − u) = −\frac{1}{2} − ∑_{j=1}^{∞} \frac{B_{j+1}}{j + 1} \frac{u^{j}}{j!} ,

we have

∑_{k=1}^{∞} g_{k}(n)\frac{x^{k}}{k} = −\frac{ny}{2} − ∑_{j=2}^{∞} \frac{B_{j}}{j} \frac{(ny)^{j}}{j!} + \frac{y}{2} + ∑_{j=2}^{∞} \frac{B_{j}}{j} \frac{y^{j}}{j!}

= −\frac{(n − 1)}{2}y − ∑_{j=2}^{∞} \frac{B_{j}}{j} (n^{j} − 1)\frac{y^{j}}{j!} .  (2.8)

Now

\frac{y^{j}}{j!} = ∑_{k=j}^{∞}(−1)^{k−j}\left[{k \atop j}\right]\frac{x^{k}}{k!} ,

so it follows from (2.8) that

g_{k}(n) = (−1)^{k} \frac{n − 1}{2} − \frac{1}{(k − 1)!} ∑_{j=2}^{k}(−1)^{k−j}\left[{k \atop j}\right]\frac{B_{j}}{j} (n^{j} − 1). □

By taking n → 0 in (2.7), we find that

∑_{k=1}^{∞} g_{k}(0)\frac{x^{k}}{k} = log \frac{x}{log(1 + x)}.

Differentiating this formula with respect to x then multiplying by x, we obtain

∑_{k=1}^{∞} g_{k}(0)x^{k} = 1 − \frac{x}{(1 + x) log(1 + x)}.

Thus g_{k}(0) = −N_{k}/k!, where the Nörlund numbers N_{k} are defined by

\frac{x}{(1 + x) log(1 + x)} = ∑_{k=0}^{∞} N_{k} \frac{x^{k}}{k!}

(see Howard [6]). So the formula for g_{k}(n) given by Theorem 2.1 may be restated as

g_{k}(n) = −\frac{N_{k}}{k!} + (−1)^{k} \frac{n}{2} − \frac{1}{(k − 1)!} ∑_{j=2}^{k}(−1)^{k−j}\left[{k \atop j}\right]\frac{B_{j}}{j} n^{j}.  (2.9)

Since \left[{k \atop k}\right] = 1 and \left[{k \atop k−1}\right] = \binom{k}{2}, for k ≥ 2 the leading term of g_{k}(n) is −(B_{k}/k!)n^{k} for k even and (k/2(k − 1)!)B_{k−1}n^{k−1} for k odd. Moreover, g_{k}(n) − (−1)^{k}n/2 contains only even powers of n.

It is clear that g_{k}(1) = 0 for every k, so g_{k}(n) is divisible by n − 1. Empirical evidence suggests that other than the fact that g_{2}(n) is divisible by n − 5, the only other factorization of the polynomials g_{k}(n) over the rationals is given by the following result.

Proposition 2.2. If k is odd, then as a polynomial in n, g_{k}(n) is divisible by n−d for every positive divisor d of k.

Proof. We shall show that if d is a positive divisor of k then g_{k}(d) = 0.

Let ξ be a primitive dth root of unity, where d is odd. We want to show that if q is odd then

∑_{j=1}^{d−1}(ξ^{j} − 1)^{−dq} = 0.

Let A be the sum in question. Then for any integer l,

A = ξ^{−dql}A = ∑_{j=1}^{d−1}(ξ^{j+l} − ξ^{l})^{−dq}.

Thus

dA = ∑_{l=0}^{d−1} ξ^{−dql}A = ∑_{{0≤l,m≤d−1 \atop l≠m}}(ξ^{m} − ξ^{l})^{−dq}.

Interchanging m and l in the last sum multiplies each term by (−1)^{dq} = −1 and also permutes the terms in the sum. Thus dA = −dA, so A = 0. □

As another example of the method of factorization, set z = (1 + x)/(1 − x) in (2.6). Then we have

\frac{(\frac{1 + x}{1 − x})^{n} − 1}{2x/(1 − x)} = ∏_{{ζ^{n}=1 \atop ζ≠1}} (\frac{1 + x}{1 − x} − ζ) .

Multiplying both sides by (1 − x)^{n−1}, dividing each side by its constant term, and simplifying, we get

\frac{(1 + x)^{n} − (1 − x)^{n}}{2nx} = ∏_{{ζ^{n}=1 \atop ζ≠1}} (1 − \frac{ζ + 1}{ζ − 1}x) .

As before, we get

log \frac{2nx}{(1 + x)^{n} − (1 − x)^{n}} = ∑_{k=1}^{∞}[ ∑_{{ζ^{n}=1 \atop ζ≠1}} (\frac{ζ + 1}{ζ − 1})^{k}]\frac{x^{k}}{k} .

If we set

q_{k}(n) = ∑_{{ζ^{n}=1 \atop ζ≠1}} (\frac{ζ + 1}{ζ − 1})^{k} ,

then q_{k}(n) is 0 for k odd, and the first few values for even k, computed from this generating function, are

\begin{aligned}q_{2}(n) & = −\frac{1}{3}(n − 1)(n − 2) \\ q_{4}(n) & = \frac{1}{45}(n − 1)(n − 2)(n^{2} + 3n − 13) \\ q_{6}(n) & = −\frac{1}{945}(n − 1)(n − 2)(2n^{4} + 6n^{3} − 28n^{2} − 96n + 251) \end{aligned}

We also have a simple trigonometric formula:

q_{k}(n) = (−1)^{k/2} ∑_{j=1}^{n−1} cot^{k} \frac{πj}{n} , k even.

It may be noted that q_{k}(n) is a special case of the “higher-dimensional Dedekind sums” studied by Zagier [11].

A more difficult application of factorization is a result of Stanley [10]:

Theorem 2.3. Let

S_{k}(n) = ∑_{{ζ^{n}=1 \atop ζ≠1}} |1 − ζ|^{−2k} .

Then

∑_{k=1}^{∞} 4^{k}S_{k}(n)x^{2k} = 1 − \frac{nx cot(n sin^{−1} x)}{\sqrt{1 − x^{2}}}.

Proof. First note that since |1 − ζ|^{−2} = 1/(1 − ζ)(1 − ζ^{−1}) = −ζ/(1 − ζ)^{2}, we have

S_{k}(n) = ∑_{{ζ^{n}=1 \atop ζ≠1}} |1 − ζ|^{−2k} = ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{(−ζ)^{k}}{(1 − ζ)^{2k}} = ∑_{j=1}^{n−1} (\frac{1}{2} csc \frac{πj}{n} )^{2k} .

Now since

\frac{d}{dx} log sin(n sin^{−1} x) = \frac{n cot(n sin^{−1} x)}{\sqrt{1 − x^{2}}},

we have

1 − \frac{nx cot(n sin^{−1} x)}{\sqrt{1 − x^{2}}} = −x\frac{d}{dx} [log \frac{sin(n sin^{−1} x)}{x}] .

So to prove Stanley’s formula we must show that

log \frac{sin(n sin^{−1} x)}{Cx} = − ∑_{k=1}^{∞} 4^{k}S_{k}(n)\frac{x^{2k}}{2k} = − ∑_{k=1}^{∞}(∑_{j=1}^{n−1} csc^{2k} \frac{πj}{n} )\frac{x^{2k}}{2k}  (2.10)

where log C is an appropriate constant of integration. Since sin(n sin^{−1} x)/Cx must have constant term 1, C must be n. Then multiplying both sides of (2.10) by 2 and exponentiating, we see that the identity to be proved is

(\frac{sin(n sin^{−1} x)}{nx})^{2} = ∏_{j=1}^{n−1} (1 − x^{2} csc^{2} \frac{πj}{n} ) .  (2.11)

The right side of (2.11) is a polynomial in x whose degree, constant terms, and roots are easily determined; so it is sufficient to show that these are the same for the left side. There is a complication due to the multiplicity 2 of most of the roots, which leads us to consider separately the cases n even and n odd.

First we examine the roots of the right side of (2.11). The right side of (2.11) vanishes for

x = ± sin \frac{πj}{n} , j = 1, 2, …, n − 1,

but since sin \frac{πj}{n} = sin \frac{π(n−j)}{n}, each ± sin \frac{πj}{n} with 1 ≤ j < n/2 appears twice as a root. Moreover, if n is even then each of ± sin \frac{π}{2} = ±1 appears once as a root. This takes care of all 2n − 2 roots.

Next we consider the left side of (2.10). It is easy to prove (e.g., by induction) that if n is odd then sin nθ is a polynomial of degree n in sin θ and if n is even then sin nθ/cos θ is a polynomial of degree n − 1 in sin θ.

Thus

sin(n sin^{−1} x) = \{ \begin{matrix}P_{n}(x), & if n is odd \\ \sqrt{1 − x^{2}} Q_{n−1}(x), & if n is even, \end{matrix}

where P_{m}(x) and Q_{m}(x) are polynomials in x of degree m.^{1} If x = ± sin \frac{πj}{n} for some integer j, then sin(n sin^{−1} x) = 0. Thus if n is odd,

(\frac{sin(n sin^{−1} x)}{nx})^{2}  (2.12)

is a polynomial of degree 2n − 2 with constant term 1 and with roots ± sin \frac{πj}{n} for j = 1, 2, …, (n − 1)/2, each with multiplicity (at least) 2; if n is even then (2.12) is a polynomial of degree 2n − 2 with constant term 1 and with roots ± sin \frac{πj}{n} for j = 1, 2, …, n/2 − 1, each with multiplicity (at least) 2 and with roots ±1 each of multiplicity (at least) 1. These facts are sufficient to establish (2.11), and thus Stanley’s formula. □

It is also possible to give an explicit formula, analogous to Theorem 2.1, for the coefficients of S_{2k}(n) in terms of Bernoulli numbers and central factorial numbers.

1It can be shown that for n odd, P_{n}(x) = (−1)^{(n−1)/2}T_{n}(x) and for n even, Q_{n−1}(x) = (−1)^{(n/2)−1}U_{n−1}(x), where T_{n}(x) and U_{n−1}(x) are the Chebyshev polynomials of the first and second kinds, defined by cos nθ = T_{n}(cos θ) and sin nθ = U_{n−1}(cos θ) sin θ.

3. Multisection.

Let R(x) be a rational function of x. Then R has a Laurent series expansion

R(x) = ∑_{i=N}^{∞} r_{i}x^{i}

By n-section of R(x) we mean the extraction of the sum of the terms r_{i}x^{i} in which i is divisible by n. It is well-known (and easy to prove) that

∑_{ζ^{n}=1} R(ζx) = n ∑_{k} r_{nk}x^{nk}.  (3.1)

In some cases, we have an explicit formula for r_{i} that we can use, with the help of (3.1), to evaluate ∑_{ζ^{n}=1} R(ζx).

We note that the method of multisection is closely related to the invariant theory method used by Stanley [10] to evaluate some generalized Dedekind sums.

As a simple example of this approach, take R(x) = x/(1 − x − x^{2}) = ∑_{i=0}^{∞} F_{i}x^{i}, the generating function for the Fibonacci numbers. It is well known that F_{i} = (α^{i} − β^{i})/(α − β), where α, β = (1 ± \sqrt{5})/2, so we have

∑_{k=0}^{∞} F_{nk}x^{nk} = ∑_{k=0}^{∞} \frac{α^{nk} − β^{nk}}{α − β} x^{nk}

= \frac{1}{α − β} (\frac{1}{1 − α^{n}x^{n}} − \frac{1}{1 − β^{n}x^{n}} )

= \frac{1}{α − β} (\frac{(α^{n} − β^{n})x^{n}}{1 − (α^{n} + β^{n})x^{n} + (αβ)^{n}x^{2n}} )

= \frac{F_{n}x^{n}}{1 − L_{n}x^{n} + (−1)^{n}x^{2n}}

where L_{n} = α^{n} + β^{n} is the nth Lucas number. Thus

∑_{ζ^{n}=1} \frac{ζx}{1 − ζx − (ζx)^{2}} = \frac{nF_{n}x^{n}}{1 − L_{n}x^{n} + (−1)^{n}x^{2n}} .  (3.2)

Although we proved (3.2) under the assumption that x is an indeterminate, since both sides are rational functions of x, (3.2) must also hold as an identity of rational functions. Thus we may set x = 1 in (3.2) to obtain

∑_{ζ^{n}=1} \frac{ζ}{1 − ζ − ζ^{2}} = \frac{nF_{n}}{1 + (−1)^{n} − L_{n}} .  (3.3)

Note that as a consequence of (3.3) we have the curious formula

lim_{n→∞} \frac{1}{n} ∑_{ζ^{n}=1} \frac{1}{1 − ζ − ζ^{2}} = −\frac{1}{\sqrt{5}}.

Next we apply multisection to prove a simple but fundamental and important result.

Theorem 3.1. Let r be an integer with 1 ≤ r ≤ n. Then if x ≠ y,

∑_{ζ^{n}=1} \frac{ζ^{r}}{x − yζ} = n\frac{x^{r−1}y^{n−r}}{x^{n} − y^{n}} .  (3.4)

Proof. Since both sides are homogeneous of degree −1 in x and y, it is sufficient to prove the case in which x = 1. Moreover, since both sides are rational functions of x and y, we may assume that y is an indeterminate, so that the left side can be expanded as a power series in y. Then since n-secting y^{r}/(1 − y) = y^{r} + y^{r+1} + ⋯ yields y^{n} + y^{2n} + ⋯ = y^{n}/(1 − y^{n}), we obtain

∑_{ζ^{n}=1} \frac{(yζ)^{r}}{1 − yζ} = \frac{ny^{n}}{1 − y^{n}} ,

and this is equivalent to the formula to be proved. □

Note that since the sum on the left side of (3.4) depends only on the congruence class of r modulo n, Theorem 3.1 can be used to evaluate this sum for all r. In particular, the case r = n is equivalent to (2.4).

Corollary 3.2. If 1 ≤ r ≤ n then

∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ^{r}}{1 − ζ} = r − \frac{n − 1}{2}.  (3.5)

Proof. By Theorem 3.1,

∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ^{r}}{1 − yζ} = n\frac{y^{n−r}}{1 − y^{n}} − \frac{1}{1 − y} .

The corollary follows by taking the limit as y → 1. □

Our next corollary generalizes (2.3) and (2.7).

Corollary 3.3. If 1 ≤ r ≤ n then

∑_{k=1}^{∞} u^{k−1} ∑_{ζ^{n}=1} \frac{ζ^{r}}{(x − yζ)^{k}} = n\frac{(x − u)^{r−1}y^{n−r}}{(x − u)^{n} − y^{n}}  (3.6)

and

∑_{k=1}^{∞} u^{k−1} ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ^{r}}{(1 − ζ)^{k}} = \frac{1}{u} + n\frac{(1 − u)^{r−1}}{(1 − u)^{n} − 1}.  (3.7)

Proof. We have

∑_{k=1}^{∞} u^{k−1} ∑_{ζ^{n}=1} \frac{ζ^{r}}{(x − yζ)^{k}} = ∑_{ζ^{n}=1} ζ^{r} ∑_{k=1}^{∞} \frac{u^{k−1}}{(x − yζ)^{k}} = ∑_{ζ^{n}=1} \frac{ζ^{r}}{x − u − yζ}

= n\frac{(x − u)^{n−r′−1}y^{r′}}{(x − u)^{n} − y^{n}} ,

which proves (3.6). To prove (3.7), subtract from (3.6) its specialization at n = 1 (and r = 1), and then set x = y = 1. □

In particular, it follows from Corollary 3.3 that

∑_{ζ^{n}=1} \frac{ζ^{r}}{(x − yζ)^{2}} = n\frac{x^{r−2}y^{n−r}((n + 1 − r)x^{n} + (r − 1)y^{n})}{(x^{n} − y^{n})^{2}},  (3.8)

which can also be obtained by differentiating (3.4) with respect to x. The case r = n of (3.8) is equivalent to (2.5).

If we take r = 1 in (3.7), we get

∑_{k=1}^{∞} u^{k−1} ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ}{(1 − ζ)^{k}} = \frac{1}{u} + \frac{n}{(1 − u)^{n} − 1}.  (3.9)

L. Carlitz [3, 4] has studied the “degenerate Bernoulli numbers” β_{k}(λ) defined by

∑_{k=0}^{∞} β_{k}(λ)\frac{u^{k}}{k!} = \frac{u}{(1 + λu)^{1/λ} − 1}.  (3.10)

Comparing (3.9) with (3.10), we see that

∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ}{(1 − ζ)^{k}} = \frac{(−1)^{k−1}}{k!} n^{k}β_{k}(1/n).  (3.11)

More generally, Carlitz [4, Section 5] considered “degenerate Bernoulli polynomials” β_{k}(λ, z) defined by

∑_{k=0}^{∞} β_{k}(λ, z)\frac{u^{k}}{k!} = \frac{u(1 + λu)^{z/λ}}{(1 + λu)^{1/λ} − 1}.  (3.12)

Taking r = s + 1 in (3.7), where 0 ≤ s ≤ n − 1, and comparing with (3.12) gives the following result:

Corollary 3.4. For 0 ≤ s ≤ n − 1,

∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{ζ^{s+1}}{(1 − ζ)^{k}} = \frac{(−1)^{k−1}}{k!} n^{k}β_{k}(1/n, s/n). □

4. Partial Fractions.

We have already seen, at least implicitly, some examples of partial fraction expansions: the logarithmic derivatives of the factorizations in section 2 are partial fraction expansions, and Theorem 3.1 may be viewed as a partial fraction expansion. Since any rational function of ζ can be expressed as polynomial plus a linear combination of rational functions of the form (1 − αζ)^{−k}, and we know how to evaluate ∑_{ζ^{n}=1}(1 − αζ)^{−k}, we can in principle evaluate any generalized Dedekind sum by partial fractions.

As a first application of this method, we consider an American Mathematical Monthly problem proposed by P. E. Bjørstad and H. Fettis [1] and solved by H.-J. Seiffert: to find a “closed algebraic expression” for the sum

S_{N} = ∑_{k=1}^{N−1} \begin{matrix}sin & 2 & \frac{kπ}{N} \\ (1 − 2a cos \frac{kπ}{N} + a^{2}) & 2 \end{matrix} .

We give a simpler derivation of Seiffert’s formula:

Proposition 4.1.

S_{N} = \frac{N}{2(1 − a^{2N})} (\frac{1 + a^{2N−2}}{1 − a^{2}} − 2N \frac{a^{2N−2}}{1 − a^{2N}} ) .

Proof. To evaluate S_{N}, we first express it as a generalized Dedekind sum. We note that the summand is an even function of k that vanishes when k is divisible by N. Thus

S_{N} = \frac{1}{2} ∑_{k=−N}^{N−1} \begin{matrix}sin & 2 & \frac{kπ}{N} \\ (1 − 2a cos \frac{kπ}{N} + a^{2}) & 2 \end{matrix} .

Expressing the trigonometric functions in terms of roots of unity, we have

S_{N} = −\frac{1}{8} ∑_{ζ^{2N} =1} \frac{(ζ − ζ^{−1})^{2}}{[(1 − aζ)(1 − aζ^{−1})]^{2}} .

Now for any integer n, let us set

T_{n} = ∑_{ζ^{n}=1} \frac{(ζ − ζ^{−1})^{2}}{[(1 − aζ)(1 − aζ^{−1})]^{2}} ,

so that S_{N} = −T_{2N}/8.

We have the partial fraction expansion

\frac{(ζ − ζ^{−1})^{2}}{[(1 − aζ)(1 − aζ^{−1})]^{2}} = \frac{1}{a^{2}} − \frac{2}{a^{2}(1 − a^{2})(1 − aζ)}

+ \frac{1}{a^{2}(1 − aζ)^{2}} + \frac{2}{(1 − a^{2})(1 − ζ/a)} + \frac{1}{a^{2}(1 − ζ/a)^{2}} .

Summing over ζ^{n} − 1, applying formulas (3.4) and (3.8), and simplifying yields

T_{n} = −\frac{2n}{1 − a^{n}} (\frac{1 + a^{n−2}}{1 − a^{2}} − n\frac{a^{n−2}}{1 − a^{n}} )

and the theorem follows. □

We now give one of the many possible generalizations of Proposition 4.1.

the electronic journal of combinatorics 4 (no. 2) (1997), #R11 13

Theorem 4.2. Let

P_{n}(k, l, r) = ∑_{ζ^{n}=1} \frac{ζ^{r}}{(1 − aζ)^{k}(1 − aζ^{−1})^{l}} .

Then if 1 ≤ r ≤ n − 1,

∑_{k,l=0}^{∞} P_{n}(k, l, r)x^{k}y^{l} = \frac{n}{(1 − x)(1 − y) − a^{2}} (x(1 − x − a^{2})\frac{(1 − x)^{r−1}a^{n−r}}{(1 − x)^{n} − a^{n}}

+ y(1 − y − a^{2})\frac{(1 − y)^{n−r−1}a^{r}}{(1 − y)^{n} − a^{n}} ),

and

∑_{k,l=0}^{∞} P_{n}(k, l, 0)x^{k}y^{l} = n + \frac{n}{(1 − x)(1 − y) − a^{2}} (x(1 − x − a^{2})\frac{(1 − x)^{n−1}}{(1 − x)^{n} − a^{n}}

+ y(1 − y − a^{2})\frac{(1 − y)^{n−1}}{(1 − y)^{n} − a^{n}} − xy),

Proof. We have

∑_{k,l=0}^{∞} P_{n}(k, l, r)x^{k}y^{l} = ∑_{k,l=0}^{∞} x^{k}y^{l} ∑_{ζ^{n}=1} \frac{ζ^{r}}{(1 − aζ)^{k}(1 − aζ^{−1})^{l}}

= ∑_{ζ^{n}=1} ζ^{r} ∑_{k,l} \frac{x^{k}y^{l}}{(1 − aζ)^{k}(1 − aζ^{−1})^{l}} .

Then

∑_{k,l=0}^{∞} \frac{x^{k}y^{l}}{(1 − aζ)^{k}(1 − aζ^{−1})^{l}} = (1 − \frac{x}{1 − aζ} )^{−1} (1 − \frac{y}{1 − aζ^{−1}} )^{−1}

= 1 + \frac{1}{(1 − x)(1 − y) − a^{2}} (\frac{x(1 − x − a^{2})}{1 − x − aζ} + \frac{y(1 − y − a^{2})}{1 − y − aζ^{−1}} − xy) .

Now multiply each side by ζ^{r} and sum over all ζ with ζ^{n} = 1. The sum can be evaluated by Theorem 3.1, using the fact that

∑_{ζ^{n}=1} \frac{ζ^{r}}{1 − y − aζ^{−1}} = ∑_{ζ^{n}=1} \frac{ζ^{−r}}{1 − y − aζ} = ∑_{ζ^{n}=1} \frac{ζ^{n−r}}{1 − y − aζ} . □

Next we show how Stanley’s formula (Theorem 2.3) can be proved by partial fractions. Although the proof we gave earlier suggested that this result depends on a very special factorization, the proof we give now shows that Stanley’s formula is an instance (though an especially nice one) of a much more general phenomenon.

To prove Stanley’s formula we must evaluate

∑_{k=1}^{∞} 4^{k}S_{k}(n)x^{2k} = ∑_{k=1}^{∞}(2x)^{2k} ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{(−ζ)^{k}}{(1 − ζ)^{2k}} = − ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ} .

We proceed by expanding

−\frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ}  (4.1)

in partial fractions. Factoring the denominator of (4.1), we find that

(1 − ζ)^{2} + 4x^{2}ζ = (1 − Aζ)(1 − Bζ),

where A = 1 − 2x^{2} + 2ix\sqrt{1 − x^{2}} and B = 1 − 2x^{2} − 2ix\sqrt{1 − x^{2}}, and we obtain the partial fraction expansion

−\frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ} = \frac{ix}{\sqrt{1 − x^{2}}} (\frac{1}{1 − Aζ} − \frac{1}{1 − Bζ} ) .

Summing over ζ^{n} = 1 yields

− ∑_{ζ^{n}=1} \frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ} = \frac{nix}{\sqrt{1 − x^{2}}} (\frac{1}{1 − A^{n}} − \frac{1}{1 − B^{n}} ) .

Since AB = 1, we have

\frac{1}{1 − A^{n}} − \frac{1}{1 − B^{n}} = \frac{1}{1 − A^{n}} − \frac{A^{n}}{A^{n} − 1} = \frac{1 + A^{n}}{1 − A^{n}} ,

and thus

− ∑_{ζ^{n}=1} \frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ} = \frac{nix}{\sqrt{1 − x^{2}}} \frac{1 + A^{n}}{1 − A^{n}} .  (4.2)

Since evaluating (4.1) at ζ = 1 yields −1, we subtract −1 from both sides of (4.2) to obtain

∑_{k=1}^{∞} 4^{k}S_{k}(n)x^{2k} = − ∑_{{ζ^{n}=1 \atop ζ≠1}} \frac{4x^{2}ζ}{(1 − ζ)^{2} + 4x^{2}ζ}

= 1 + \frac{nix}{\sqrt{1 − x^{2}}} \frac{1 + (1 − 2x^{2} + 2ix\sqrt{1 − x^{2}})^{n}}{1 − (1 − 2x^{2} + 2ix\sqrt{1 − x^{2}})^{n}} .  (4.3)

To see that (4.3) really is equivalent to Theorem 2.3, we make the substitution x = sin θ, which takes A to cos 2θ + i sin 2θ = e^{2iθ}. Then (4.3) becomes

∑_{k=1}^{∞} 4^{k}S_{k}(n) sin^{2k} θ = 1 + ni tan θ \frac{1 + e^{2iθn}}{1 − e^{2iθn}} ,

from which the equivalence is clear.

We can apply the same approach to ∑_{k=1}^{∞} x^{k} ∑_{ζ^{n}=1} R(ζ)^{k} in the general case.

Theorem 4.3. Let R(ζ) be a rational function defined for every root of unity ζ. Then

∑_{k=1}^{∞} x^{k} ∑_{ζ^{n}=1} R(ζ)^{k} = nT (x) + n ∑_{j} \frac{N_{j}(x)}{1 − D_{j}(x)^{n}} ,  (4.4)

where T (x) is a rational function of the form ax/(b + cx) and N_{j}(x) and D_{j}(x) are algebraic functions, with D_{j}(x) ≠ 0.

Proof. Let R(ζ) = P (ζ)/Q(ζ), for relatively prime polynomials P and Q. Then

∑_{k=1}^{∞} x^{k} ∑_{ζ^{n}=1} R(ζ)^{k} = ∑_{ζ^{n}=1} \frac{xR(ζ)}{1 − xR(ζ)} = ∑_{ζ^{n}=1} \frac{xP (ζ)}{Q(ζ) − xP (ζ)}.

Now Q(ζ) − xP (ζ) may be factored as C(x) ∏_{j}(1 − D_{j}(x)ζ) for some algebraic functions C(x) and D_{j}(x), and it is not difficult to show that the D_{j} must be distinct (since Q(ζ) − xP (ζ) is irreducible over C(x)[ζ]). Thus xP (ζ)/(Q(ζ) − xP (ζ)) has a partial fraction decomposition

\frac{xP (ζ)}{Q(ζ) − xP (ζ)} = T (x) + ∑_{j} \frac{N_{j}(x)}{1 − D_{j}(x)ζ} ,

where the N_{j}(x) and D_{j}(x) are algebraic functions of x, and T (x) is a rational function of x. More precisely T (x) is 0 if the degree of P is less than that of Q, T (x) is −1 if the degree of P is greater, and if P and Q have the same degree, with leading coefficients p and q, then T (x) = px/(q − px). Summing over ζ^{n} = 1 yields

∑_{k=1}^{∞} x^{k} ∑_{ζ^{n}=1} R(ζ)^{k} = nT (x) + n ∑_{j} \frac{N_{j}(x)}{1 − D_{j}(x)^{n}} . □

A similar result holds for ∑_{k=1}^{∞} x^{k} ∑_{{ζ^{n}=1 \atop ζ≠1}} R(ζ)^{k}: the right side of (4.4) is modi-

fied by subtracting xP (1)/(Q(1)−xP (1)), which is always well-defined even if R(1) is not. Usually when ζ = 1 is omitted from the sum it is because Q(1) = 0, and in this case xP (1)/(Q(1) − xP (1)) = −1, as in our second proof of Stanley’s formula.

Finally, we give an example of a “reciprocity theorem.”

Theorem 4.4. Let m and n be relatively prime and suppose that 0 ≤ r < m + n. Then

\frac{1}{m} ∑_{{ζ^{m}=1 \atop ζ≠1}} \frac{ζ^{r+1}}{(ζ^{n} − 1)(ζ − 1)} + \frac{1}{n} ∑_{{η^{n}=1 \atop η≠1}} \frac{η^{r+1}}{(η^{m} − 1)(η − 1)}

= −\frac{1}{12} (\frac{m}{n} + \frac{n}{m} + \frac{1}{mn}) + \frac{1}{4} (\frac{1}{m} + \frac{1}{n} − 1) + \frac{r}{2} (\frac{1}{m} + \frac{1}{n} − \frac{1}{mn}) − \frac{r^{2}}{2mn}.

Proof. First we find the partial fraction expansion of x^{r}/(x^{m} − 1)(x^{n} − 1), which is a proper rational function since r < m+n. If ζ^{m} = 1 but ζ ≠ 1, then the coefficient of 1/(x − ζ) in the partial fraction expansion is

\frac{ζ^{r}}{ζ^{n} − 1} lim_{x→ζ} \frac{x − ζ}{x^{m} − 1} = \frac{ζ^{r}}{ζ^{n} − 1} · \frac{1}{mζ^{m−1}} = \frac{ζ^{r+1}}{m(ζ^{n} − 1)}.

The coefficent of 1/(x − η), where η^{n} = 1 but η ≠ 1, is computed similarly. The coefficients of 1/(x−1)^{2} and 1/(x−1) in the partial fraction expansion are the same as the coefficients of 1/(x−1)^{2} and 1/(x−1) in the expansion of x^{r}/(x^{m}−1)(x^{n}−1) as a Laurent series in powers of x − 1. To compute these coefficients, let us make the substitution x = z + 1, so z = x − 1. Then

\frac{1}{x^{m} − 1} = \frac{1}{(1 + z)^{m} − 1} = \frac{1}{mz + \binom{m}{2}z^{2}} = \frac{1}{mz} − \frac{m − 1}{2m} + positive powers of z,

and similarly for 1/(x^{n} − 1). So

\frac{x^{r}}{(x^{m} − 1)(x^{n} − 1)} = (1 + z)^{r} (\frac{1}{mz} − \frac{m − 1}{2m} + ⋯) (\frac{1}{nz} − \frac{n − 1}{2n} + ⋯)
= \frac{1}{mnz^{2}} − \frac{m + n − 2r − 2}{2mnz} + nonnegative powers of z.

(Alternatively, we can compute the needed terms of the Laurent series directly with Maple or some other computer algebra system.)

Thus the partial fraction expansion of x^{r}/(x^{m} − 1)(x^{n} − 1) is

\frac{x^{r}}{(x^{m} − 1)(x^{n} − 1)} = \frac{1}{mn(x − 1)^{2}} − \frac{m + n − 2r − 2}{2mn(x − 1)}

+ ∑_{{ζ^{m}=1 \atop ζ≠1}} \frac{ζ^{r+1}}{m(ζ^{n} − 1)(x − ζ)} + ∑_{{η^{n}=1 \atop η≠1}} \frac{η^{r+1}}{n(η^{m} − 1)(x − η)}.

Now subtract the terms in negative powers of x − 1 from both sides, and take the limit as x → 1. We obtain

\frac{1}{12} (\frac{m}{n} + \frac{n}{m} + \frac{1}{mn}) + \frac{1}{4} (1 − \frac{1}{m} − \frac{1}{n}) + \frac{r}{2} (\frac{1}{mn} − \frac{1}{m} − \frac{1}{n}) + \frac{r^{2}}{2mn}

= ∑_{{ζ^{m}=1 \atop ζ≠1}} \frac{ζ^{r+1}}{m(ζ^{n} − 1)(1 − ζ)} + ∑_{{η^{n}=1 \atop η≠1}} \frac{η^{r+1}}{n(η^{m} − 1)(1 − η)}. □

The reciprocity theorem for the classical Dedekind sum is easily derived from the case r = 0 of Theorem 4.4 (see [7, Chapter 2]). Carlitz [2] has given a proof related to this one, but based on the partial fraction expansion of (x − 1)/(x^{m} − 1)(x^{n} − 1), which he derives from the Lagrange interpolation formula. See also Zagier [11] for a far-reaching generalization proved using residues (which for rational functions are equivalent to partial fraction expansion).

References

1. P. E. Bjørstad and H. Fettis, Asymptotic formulas from Chebyshev polynomials, Problem 6332, Solution by H.-J. Seiffert, Amer. Math. Monthly 88 (1994), 1015–1017.

2. L. Carlitz, The reciprocity formula for Dedekind sums, Pacific J. Math. 3 (1953), 523–527.

3. L. Carlitz, A degenerate Staudt-Clausen theorem, Archiv der Mathematik 7 (1956), 28–33.

4. L. Carlitz, Degenerate Stirling, Bernoulli, and Eulerian numbers, Utilitas Math. 15 (1979), 51–88.

5. A. J. Duran, A sequence of polynomials related to roots of unity, Problem E 3339, Solution by R. J. Chapman and R. W. K. Odoni, Amer. Math. Monthly 98 (1991), 269-271.

6. F. T. Howard, Nörlund’s number B_{n}^{(n)}, Applications of Fibonacci Numbers, Vol. 5 (G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds.), Kluwer Acad. Publ., Dordrecht, 1993, pp. 355–366.

7. H. Rademacher and E. Grosswald, Dedekind Sums, Carus Mathematical Monographs, No. 16, Mathematical Association of America, 1972.

8. L. Smith, The e-invariant and finite coverings, Indiana Math. J. 24 (1975), 659–675.

9. L. Smith, personal communication, 1993.

10. R. P. Stanley, Invariants of finite groups and their applications to combinatorics, Bull. Amer. Math. Soc. (N.S.) 1 (1979), 475–511.

11. D. Zagier, Higher dimensional Dedekind sums, Math. Ann. (1973), 149–172.