SORTING ALGORITHMS FOR BROADCAST COMMUNICATIONS: MATHEMATICAL ANALYSIS

PETER J. GRABNER^{†} AND HELMUT PRODINGER

Abstract. We study three algorithms for sorting under the broadcast communication model. Two algorithms are based on the maximum finding and the loser selection strategy, the third one is the naïve strategy based on loser selection only. While a precise description of the algorithms can be found in the paper [15], we concentrate here on the mathematical aspects of the analysis. From these elementary considerations it follows that the average time complexities of the non-naïve algorithms are Θ(n). We give precise expressions for the constants involved by writing them as contour integrals involving zeta functions. The numerical evaluation via residues leads to slowly converging series, and the acceleration of them is a nontrivial task that is done in a slightly more general fashion in order to fit all the applications.

1. Introduction

The purpose of this paper is two-fold: firstly we discuss a probabilistic model for conflict resolution in broadcast communication and secondly we present a method to compute certain integrals which occur in the asymptotic analysis of this model (and also elsewhere) numerically to a high precision.

Let us first describe the model: Assume that n persons communicate via a channel. Several algorithms related to the transmitted data (“numbers”) are of interest. A particularly simple one is to find the maximum of the n items (communicated by the n persons). This algorithm was formulated and analyzed in [13, 5]. A more complex task is sorting: in the end every party should have a complete sorted list of the n items. This implies of course that every item has to be communicated at some stage.

We will analyze three algorithms to achieve this; the interest is in the average number of discrete time slots needed for communicating data (number of “rounds”).

When more than one person sends at a time, a conflict arises. The conflict resolution schemes that are considered here are all based on coin flippings (with a fair coin): The persons involved in a conflict flip a coin, and those who flipped tail step out and wait until those who flipped head have resolved their conflict.

This principle is often described as “selection of a loser”, see [6, 11], or as leader election, see [12, 3, 8]. (The loser is determined by consecutive rounds of coin flippings; those who flip heads create smaller and smaller populations until a single person remains. There is a special rule to be applied however when nobody flips head; then this round has to be repeated.) The loser then successfully transmits his data. By different recursive strategies we obtain the variants of the algorithm studied in this paper.

Date: January 16, 2001.

1991 Mathematics Subject Classification. Primary: 68Q25; Secondary: 05A15, 05A16, 60C05.

† This author is supported by the START-project Y96-MAT of the Austrian Science Foundation.

Section 2: The first algorithm uses the maximum finding strategy as studied in [13, 5]. Finding the maximum needs several rounds of recursive coin flippings; after each successful broadcast of a number only the persons with larger numbers than the announced one go on recursively. Thus, in the process of finding the maximum, several data items have already been transmitted successfully (and are known to all participants). The remaining set of persons, who have not yet transmitted their data successfully, follows the same strategy recursively, until no persons are left. See [14] for a more detailed description of the algorithm.

Section 3: The second algorithm does not use the maximum finding strategy, but loser selection instead. The loser transmits his number, and the participants are split into two subfiles (larger resp. smaller numbers). These two subfiles are processed recursively, until all persons have broadcasted. See [15] for a detailed description.

Section 4: Finally, we discuss a very naïve strategy, where we only record the communication provided by the loser, and find the next loser from the reduced set of n − 1 persons, etc. This is naturally slower.

Loser selection works by coin flippings; the first two algorithms use additionally a splitting à la binary search, whereas the naïve strategy only works sequentially. It turns out that the second algorithm is the best, the intuitive reason being perhaps that it is good to split the file as soon as possible, i. e. when the first loser has been found.

We remark that in our probabilistic model we use independent unbiased coins for selecting the losers. Furthermore, all permutations of data are equally likely (as it si customary when analyzing sorting algorithms).

The average number of rounds to select a loser is given by the recursion

S_{n}(1 − 2^{−n}) = 1 + 2^{−n} ∑_{k=0}^{n} \binom{n}{k}S_{k}, n ≥ 2, S_{0}, S_{1} = 0.

(Note that this algorithm itself is recursive).

From [11] we know the solution

S_{n} = 1 − ∑_{k=1}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k} − 1}, n ≥ 2

with Bernoulli numbers B_{k}.

There is also the very useful representation of S_{n} as a contour integral, viz.

S_{n} = 1 − \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(1 − s)Γ(n + 1)ζ(1 − s)}{Γ(n + 1 − s)(2^{s} − 1)} ds.

See [4] for some background on such integrals.

The average number of rounds M_{n} to find the maximum [13, 5] is given by

M_{n} = 1 + ∑_{k=0}^{n−1} \frac{2B_{k}}{1 − 2^{−k−1}} [\binom{n}{k + 1} − 1],  n ≥ 0;

it was also proved that

M_{n} − M_{n−1} = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{Γ(n)Γ(1 − s)}{Γ(n − s)} \frac{2ζ(1 − s)}{1 − 2^{−s−1}} ds.  (1)

Several parameters of the probabilistic model described above can be expressed in terms of series involving the sequences M_{n} and S_{n}. These series turn out to converge very slowly so that they are not even suitable to compute three digits of the values in question. In the specific case here the second possibility to compute these constants is also not applicable: deform the line of integration in the contour integral representation and collect residues (cf. section 5). Here the resulting series is again converging too slowly. In section 6 we will describe how to use the integral representation to obtain a rapidly converging algorithm for numerical computation of these integrals. This algorithm is formulated rather general and could be applied to similar problems immediately.

Remark. If the only task were to transmit all the elements, then the most obvious strategy is the conflict resolution scheme as described in [9]; all participants try to broadcast in the beginning, and then the conflict is resolved by consecutive rounds of coin flippings. The average number of rounds for this procedure is (apart from small fluctuations) asymptotically equal to \frac{2}{log 2}n; the constant \frac{2}{log 2} = 2.885390082 is better than the constants for the algorithms in this paper. However, in this way the data arrive in random order, whereas the strategies in this paper produce the sorted file (one can think about the data as arranged in the Quicksort tree [12]).

2. The maximum finding strategy

Denote by T_{n} the average number of rounds with this method. Shiau and Yang [14] argue like this: There are extra costs of M_{n} for finding the maximum on the first level of recursion. The first successful broadcast, which can be any element with the same probability \frac{1}{n}, splits the file into a subfile of n−k−1 smaller elements to which the recursive strategy is applied at a later stage, with costs T_{n−k−1}. In the file of k larger elements, the search for the maximum is still continuing, but we have taken care already for the extra cost for maximum searching, thus a contribution T_{k} − M_{k}. If k = 0, it costs however 0, and if k = 1, it costs 1, so that we have the recursion for n ≥ 2

T_{n} = M_{n} + \frac{1}{n} ∑_{k=0}^{n−1} T_{k} + \frac{1}{n} ∑_{k=2}^{n−1}(T_{k} − M_{k}) + \frac{1}{n},

with T_{0} = 1 and T_{1} = 1.

We multiply that by n:

nT_{n} = nM_{n} + ∑_{k=0}^{n−1} T_{k} + ∑_{k=2}^{n−1}(T_{k} − M_{k}) + 1,

write this with n replaced by n − 1:

(n − 1)T_{n−1} = (n − 1)M_{n−1} + ∑_{k=0}^{n−2} T_{k} + ∑_{k=2}^{n−2}(T_{k} − M_{k}) + 1,

and take differences:

nT_{n} − (n − 1)T_{n−1} = nM_{n} − (n − 1)M_{n−1} + T_{n−1} + T_{n−1} − M_{n−1},

or (replacing n by k)

\frac{T_{k}}{k + 1} − \frac{T_{k−1}}{k} = \frac{M_{k} − M_{k−1}}{k + 1} .

Summing this from k = 3, …, n we get

\frac{T_{n}}{n + 1} − \frac{T_{2}}{3} = ∑_{k=3}^{n} \frac{M_{k} − M_{k−1}}{k + 1}

or

T_{n} = \frac{13}{6}(n + 1) + (n + 1) ∑_{k=3}^{n} \frac{M_{k} − M_{k−1}}{k + 1} for n ≥ 2.

Since asymptotics of M_{n} are well–known [5] we know a priori that T_{n} ∼ A_{1} · n, where the constant A_{1} is given by

A_{1} = \frac{13}{6} + ∑_{k=3}^{∞} \frac{M_{k} − M_{k−1}}{k + 1} .

(With more effort, one could derive a full asymptotic expansion; see section 6 for such computations.)

Using (1) we obtain

∑_{k=3}^{∞} \frac{1}{k + 1}(M_{k} − M_{k−1}) = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}∑_{k=3}^{∞} \frac{Γ(k)Γ(1 − s)}{(k + 1)Γ(k − s)} \frac{2ζ(1 − s)}{1 − 2^{−s−1}} ds.  (2)

Define

f(s) := Γ(1 − s) ∑_{n=3}^{∞} \frac{Γ(n)}{(n + 1)Γ(n − s)} = −\frac{6s^{2} − 3s − 5}{6(s − 1)} − s(s + 1)ψ′(−s),  (3)

SORTING ALGORITHMS FOR BROADCAST COMMUNICATIONS 5

where as usual ψ(s) = \frac{Γ′(s)}{Γ(s)}. Equation (3) is a immediate consequence of the following chain of equations (cf. [2]):

ψ′(z) = − ∫_{0}^{1} \frac{t^{z−1}}{1 − t} log t dt = − ∫_{0}^{1} \frac{(1 − t)^{z−1}}{t} log(1 − t) dt

= ∑_{n=1}^{∞} \frac{1}{n} ∫_{0}^{1}(1 − t)^{z−1}t^{n−1} dt = ∑_{n=1}^{∞} \frac{1}{n} \frac{Γ(z)Γ(n)}{Γ(n + z)}

= \frac{1}{z} + ∑_{n=2}^{∞} (\frac{Γ(z)Γ(n − 1)}{Γ(n + z)} − \frac{Γ(z)Γ(n − 1)}{nΓ(n + z)}) = \frac{1}{z} + \frac{1}{z^{2}} − ∑_{n=1}^{∞} \frac{Γ(z)Γ(n)}{(n + 1)Γ(n + z)}.

(4)

As ψ(s) is given by the uniformly convergent expansion

ψ′(s) = ∑_{n=0}^{∞} \frac{1}{(n + s)^{2}}

it is easy to see that ψ has double poles at the negative integers. For further details on ψ we refer to [2, 10, 16]. Furthermore, we note that (cf. [1]) for | arg(−s)| < π

ψ′(−s) = −\frac{1}{s} + \frac{1}{2s^{2}} − \frac{1}{6s^{3}} + \frac{1}{30s^{5}} + O(|s|^{−7}).

Using the identity

ψ′(s) + ψ′(−s) = \frac{π^{2}}{sin^{2} πs} + \frac{1}{s^{2}}

we can find an estimate valid for all s with ∀n ∈ ℕ_{0} : |s − n| > ε:

f(s) = O (\frac{1}{|s|^{2}} + \frac{1}{ε^{2}} e^{−2π|ℑs|}) .  (5)

Our goal is to compute the integral

\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}f(s)\frac{2ζ(1 − s)}{1 − 2^{−s−1}} ds.

Expanding the ζ–function and the geometric series it is

∑_{k≥1} \frac{1}{k} ∑_{j≥0} 2^{1−j} \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}f(s)(\frac{k}{2^{j}} )^{s} ds.

For the evaluation of the integral we need now

Φ(x) := \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}f(s)x^{s} ds = \begin{cases}0 & for x ≥ 1 \\ \frac{(3 − x)(1 + x + x^{2})}{3(1 − x)^{2}} + \frac{2x log x}{(1 − x)^{3}} & for 0 < x < 1. \end{cases} (6)

This equation is achieved as follows (this is actually a standard technique in analytic number theory): to obtain the formula for x ≥ 1 consider the integral over the segment \{−\frac{1}{2} + it | −R ≤ t ≤ R\} and the arc \{σ + it | σ^{2} + t^{2} = R^{2}, σ < −\frac{1}{2}\}. Since the integrand has no poles in this region, the integral vanishes; now let R tend to ∞ and observe that the estimate (5) implies that the integral over the arc tends to 0. For x < 1 we shift the line of integration to the right (technically, we again truncate the integral at t = ±R and show that the contribution tends to 0 for R → ∞) and collect residues:

\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}f(s)x^{s} ds = − ∑_{k=1}^{K} Res_{s=k} \{f(s)x^{s}\} + \frac{1}{2πi} ∫_{K+ \frac{1}{2} −i∞}^{K+ \frac{1}{2} +i∞}f(s)x^{s} ds.

By (5) the integral is bounded by O(x^{K}), which allows the limit K → ∞. Computing the residues and summing up yields the desired result.

Using (6) we obtain

∑_{k≥1} \frac{1}{k} ∑_{j≥0} 2^{1−j} \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} f(s)(\frac{k}{2^{j}} )^{s} ds = 2 ∑_{j≥0} ∑_{1≤k<2^{j}} \frac{2^{−j}}{k} Φ(\frac{k}{2^{j}} ).

Observe that Φ(1) = 0, so that we can add the term k = 2^{j} to the sum.

In section 6 we will explain how to compute such sums numerically to a high precision. Therefore we get

A_{1} = \frac{13}{6} + 2Σ_{1} = 3.67982 61095 85742 29512 70603 33235 96302 23675 …

Note that the paper [14] provides the elementary bounds \frac{7}{2} = 3.5 ≤ A_{1} ≤ \frac{23}{6} = 3.833 · · ·.

3. The splitting strategy

It is not hard to find a recursion for T_{n}, the average number of rounds for this method. (We use the notation T_{n} again, but there is no chance for confusion.) The values T_{0} = 1 and T_{1} = 1 are self-explanatory, and for n ≥ 2 we have

T_{n} = 1 + S_{n} + \frac{1}{n} ∑_{k=0}^{n−1}(T_{k} + T_{n−1−k});

the 1 counts the initial broadcast, causing the conflict, which needs S_{n} to be resolved. Then, the probability is uniformly \frac{1}{n} that the file splits. (See [15] for a more elaborate description.)

The traditional method to solve that is as in the previous section:

nT_{n} = n + nS_{n} + 2 ∑_{k=0}^{n−1} T_{k};

SORTING ALGORITHMS FOR BROADCAST COMMUNICATIONS 7

replace n by n − 1

(n − 1)T_{n−1} = n − 1 + (n − 1)S_{n−1} + 2 ∑_{k=0}^{n−2} T_{k}

and subtract to get

nT_{n} − (n + 1)T_{n−1} = 1 + nS_{n} − (n − 1)S_{n−1}.

Divide this by n(n + 1):

\frac{T_{n}}{n + 1} − \frac{T_{n−1}}{n} = \frac{1}{n} − \frac{1}{n + 1} + \frac{S_{n}}{n + 1} − \frac{n − 1}{n(n + 1)}S_{n−1}

and sum this from n = 3, …, N, but write again n for N:

\frac{T_{n}}{n + 1} − \frac{5}{3} = \frac{1}{3} − \frac{1}{n + 1} + ∑_{k=3}^{n} \frac{S_{k}}{k + 1} + ∑_{k=3}^{n} (\frac{1}{k} − \frac{2}{k + 1})S_{k−1}

or

\frac{T_{n}}{n + 1} = 2 − \frac{1}{n + 1} − \frac{S_{n}}{n + 1} + \frac{2}{3} + 2 ∑_{k=3}^{n} \frac{S_{k}}{k + 1} − 2 ∑_{k=3}^{n} \frac{S_{k−1}}{k + 1}

from which we conclude that

T_{n} = \frac{8}{3}n + \frac{5}{3} − S_{n} + 2(n + 1) ∑_{k=3}^{n} \frac{S_{k} − S_{k−1}}{k + 1} for n ≥ 2.

(In [15] this is slightly wrong.) We know again a priori that T_{n} ∼ A_{2}·n. Our aim is compute this constant A_{2}:

A_{2} = \frac{8}{3} + 2 ∑_{k=3}^{∞} \frac{S_{k} − S_{k−1}}{k + 1} .  (7)

From the integral formula for S_{k} we conclude that

S_{k} − S_{k−1} = −\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(1 − s)Γ(k + 1)ζ(1 − s)}{Γ(k + 1 − s)(2^{s} − 1)} ds + \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(1 − s)Γ(k)ζ(1 − s)}{Γ(k − s)(2^{s} − 1)} ds

= −\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{sΓ(1 − s)Γ(k)ζ(1 − s)}{Γ(k + 1 − s)(2^{s} − 1)} ds.

Define

f(s) = Γ(1 − s) ∑_{k≥3} \frac{1}{k + 1} \frac{Γ(k)}{Γ(k + 1 − s)},

8 P. J. GRABNER AND H. PRODINGER

which makes sense for ℜs < 1. The identity

f(s) = \frac{6s^{2} − 15s + 4}{6(s − 1)(s − 2)} − \frac{1}{s} + sψ′(−s)

is again a consequence of (4) and provides the analytic continuation of f(s). Then

A_{2} = \frac{8}{3} + 2 · \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{sf(s)ζ(1 − s)}{2^{s} − 1} ds.

Note that

\frac{1}{2^{s} − 1} = ∑_{k≥1} 2^{−ks}.

Therefore

\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{sf(s)ζ(1 − s)}{2^{s} − 1} ds = ∑_{k≥1} \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}sf(s)ζ(1 − s)2^{−ks} ds.

The integral

\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}sf(s)ζ(1 − s)2^{−ks} ds

can be computed by shifting the line of integration to ℜs = −\frac{1}{2} (again this is justified by the growth rate of the integrand) and expanding the ζ–function:

∑_{n=1}^{∞} \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}sf(s)n^{s−1}2^{−ks} ds.

Thus it remains to compute the function

Ψ(x) = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}sf(s)x^{s} ds.

This is done in a similar way as above and gives

Ψ(x) = \begin{cases}\frac{x(17 − 14x + 13x^{2} − 4x^{3})}{6(x − 1)^{2}} − \frac{x + x^{2}}{(x − 1)^{3}} log x & for 0 < x ≤ 1 \\ 0 & for x > 1. \end{cases}

With this notation, the constant A_{2} evaluates to

A_{2} = \frac{8}{3} + 2 ∑_{j≥0} ∑_{1≤k<2^{j}} \frac{1}{k}Ψ(\frac{k}{2^{j}} ) = 3.54551 78132 67322 88513 75825 40856 52901 34887 …

(see the last section for such evaluations).

Note also that the paper [15] gives the bounds (after correcting the simple error) 3.33 ⋯ ≤ A_{2} ≤ 4.

4. The naïve strategy

The average cost of selecting one loser is given by c_{n} = 1 + S_{n} with the quantities S_{n} from the introduction. Thus we have

c_{n} = 2 − ∑_{k=1}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k} − 1}.

In total, we need to evaluate

C_{n} = c_{1} + ⋯ + c_{n}.

We know

∑_{k=1}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k} − 1} = \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(n + 1)Γ(1 − s)}{Γ(n + 1 − s)} \frac{ζ(1 − s)}{2^{s} − 1} ds;

since c_{1} = 1 and c_{2} = 3 this leads to

C_{n} = 2n − ∑_{k=3}^{n} \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(k + 1)Γ(1 − s)}{Γ(k + 1 − s)} \frac{ζ(1 − s)}{2^{s} − 1} ds.

As before we sum up the terms in the integral

∑_{k=3}^{n} \frac{Γ(k + 1)Γ(1 − s)}{Γ(k + 1 − s)} = \frac{Γ(n + 2)Γ(1 − s)}{(s + 1)Γ(n + 1 − s)} − \frac{6}{(s − 1)(s − 2)(s + 1)}

and obtain

\begin{matrix}C_{n} = 2n+ & \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)} \frac{ζ(1 − s)}{2^{s} − 1} ds \\ − & \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{Γ(n + 2)Γ(1 − s)}{(s + 1)Γ(n + 1 − s)} \frac{ζ(1 − s)}{2^{s} − 1} ds. \end{matrix}  (8)

For further reference we denote

I = \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)} \frac{ζ(1 − s)}{2^{s} − 1} ds.

Now we use

\frac{Γ(n + 2)}{Γ(n + 1 − s)} = n^{s+1} (1 − \frac{(s − 3)(s + 1)}{2n} + O(\frac{|s|^{4}}{n^{2}} ))  (9)

(cf. [1]) to obtain

\begin{matrix}C_{n} = 2n + I− & \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}Γ(1 − s)\frac{ζ(1 − s)}{2^{s} − 1}n^{s+1} ds \\ + & \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}Γ(1 − s)\frac{(s − 3)(s + 1)}{2} \frac{ζ(1 − s)}{2^{s} − 1}n^{s} ds + O(n^{− \frac{1}{2}} ). \end{matrix}  (10)

We shift the line of integration to ℜs = −\frac{1}{2} and obtain by calculating the residues at the poles on the line ℜs = 0

C_{n} = 2n + I − \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}Γ(1 − s)\frac{ζ(1 − s)}{2^{s} − 1}n^{s+1} ds

+ \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}Γ(1 − s)\frac{(s − 3)(s + 1)}{2} \frac{ζ(1 − s)}{2^{s} − 1}n^{s} ds + n log_{2} n − \frac{1}{2}n + nF (log_{2} n)

+ \frac{3}{2} log_{2} n + \frac{1}{log 2} − \frac{3}{4} + G(log_{2} n) + O(n^{− \frac{1}{2}} ),

where F and G denote two periodic continuous functions of period 1 and mean 0 given by their Fourier-expansions (χ_{k} = \frac{2kπi}{log 2})

F (x) = −\frac{1}{log 2} ∑_{k∈ℤ\\{0\}}Γ(1 − χ_{k})ζ(1 − χ_{k})e^{2kπix}

G(x) = −\frac{1}{2 log 2} ∑_{k∈ℤ\\{0\}}(1 + χ_{k})(3 − χ_{k})Γ(1 − χ_{k})ζ(1 − χ_{k})e^{2kπix}.

(11)

It remains to compute the integral I. This is done as follows:

I = ∑_{k=1}^{∞} \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)}ζ(1 − s)2^{−ks} ds

= ∑_{k=1}^{∞} (\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)}ζ(1 − s)2^{−ks} ds − 3)

= ∑_{k=1}^{∞} ∑_{n=1}^{∞} (\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)}n^{s−1}2^{−ks} ds − 3).

As before we compute the integral

\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{6}{(s − 1)(s − 2)(s + 1)}x^{s} ds = \begin{cases}3x − 2x^{2} & for 0 < x ≤ 1 \\ \frac{1}{x} & for x > 1. \end{cases}

We obtain

I = ∑_{k=1}^{∞} ( ∑_{n=1}^{2^{k}} \frac{1}{n} (3 (\frac{n}{2^{k}} ) − 2 (\frac{n}{2^{k}} )^{2}) + 2^{k} ∑_{n=2^{k}+1}^{∞} \frac{1}{n^{2}} − 3).

After summing up the first sum and some obvious cancellation we arrive at

I = ∑_{k=1}^{∞} (2^{k} ∑_{n=2^{k}}^{∞} \frac{1}{n^{2}} − 1) − 2.

This can be computed by the methods outlined in section 6; the numerical value is given by

I = −1.44637 64113 48039 93349 42661 97916 01589 56591 06916 ….

This gives

C_{n} = n log_{2} n + \frac{3}{2}n + nF (log_{2} n) + \frac{3}{2} log_{2} n + B + G(log_{2} n) + O(n^{− \frac{1}{2}} )

with

B = \frac{1}{log 2} − \frac{3}{4} + I = −0.75368 13704 59076 52613 43415 16914 12375 82324 60962 ….

5. Mellin Integrals

One possible way to give a reasonably convergent series expansion for the value of an integral of the form

\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}f(s)\frac{ζ(1 − s)}{2^{s} − 1} ds  (12)

would be to move the line of integration to the left. This yields

\frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}f(s)\frac{ζ(1 − s)}{2^{s} − 1} ds = ∑_{k∈ℤ} Res_{s=χ_{k}} \{f(s)\frac{ζ(1 − s)}{2^{s} − 1}\} + \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}f(s)\frac{ζ(1 − s)}{2^{s} − 1} ds, (13)

where again χ_{k} = \frac{2kπi}{log 2}. Under the growth condition |f(s)| = O(|s|^{−2}) the last integral is zero by the same arguments as used above. Thus we have a series expansion for the integral (12)

\frac{1}{log 2} ∑_{k∈ℤ\\{0\}}f(χ_{k})ζ(1 − χ_{k}) + Res_{s=0} \{f(s)\frac{ζ(1 − s)}{2^{s} − 1}\}.  (14)

Unfortunately, the rate of convergence of this sum is not much better than the rate of convergence of the sums (2) and (7). Thus this method does not yield a numerically feasible method to compute integrals of the form (12) to high precision, although it is possible to get a few digits by using (14), as pointed by one of the referees. The next section will describe how to find high precision approximations to the numerical value of such integrals.

6. How to compute the integrals numerically

In this section we discuss how to compute a sums like

Σ_{1} = ∑_{j≥0} ∑_{1≤k<2^{j}} \frac{2^{−j}}{k} Φ(\frac{k}{2^{j}} ) and Σ_{2} = ∑_{j≥0} ∑_{1≤k<2^{j}} \frac{1}{k}Φ(\frac{k}{2^{j}} )  (15)

numerically. We assume that Φ ∈ C^{2m}(0, 1], Φ(0) = D, and

\frac{Φ(t) − D}{t} = ∑_{ℓ=0}^{2m} C_{ℓ}t^{ℓ} log t + Q_{2m}(t) + O(t^{2m+1} log t),  (16)

where Q_{2m} ∈ C^{2m+1}[0, 1] and C_{ℓ} are constants (these two properties are satisfied for the functions to which these studies will be applied later).

In the sequel we will use the Bernoulli-polynomials P_{k}(t) defined by

∑_{ℓ=0}^{∞} P_{ℓ}(t)\frac{z^{ℓ}}{ℓ!} = \frac{ze^{zt}}{e^{z} − 1}

and the Bernoulli numbers B_{ℓ} = P_{ℓ}(0). Throughout this section we use the notation {x} to indicate the fractional part of x.

Then we have

∑_{1≤k≤2^{j}} \frac{1}{k}f(\frac{k}{2^{j}} ) = ∑_{k=1}^{2^{j}} \frac{1}{k} (f(\frac{k}{2^{j}} ) − D) + D ∑_{k=1}^{2^{j}} \frac{1}{k}

= ∑_{k=1}^{2^{j}} \frac{1}{k} (f(\frac{k}{2^{j}} ) − D)

+ D(j log 2 + γ + \frac{1}{2^{j+1}} − ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} \frac{1}{2^{2ℓj}} + 2^{−(2m+1)j} ∫_{1}^{∞}P_{2m+1}(\{2^{j}x\})x^{−2m−2} dx)

= 2^{−j} ∑_{k=1}^{2^{j}} [\frac{2^{j}}{k} (f(\frac{k}{2^{j}} ) − D) − ∑_{ℓ=0}^{2m} C_{ℓ}(\frac{k}{2^{j}} )^{ℓ} log \frac{k}{2^{j}} ]

+ ∑_{ℓ=0}^{2m} C_{ℓ}2^{−j} ∑_{k=1}^{2^{j}} (\frac{k}{2^{j}} )^{ℓ} log \frac{k}{2^{j}} + D(j log 2 + γ + \frac{1}{2^{j+1}} − ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} \frac{1}{2^{2ℓj}} + R_{j})

where |R_{j}| ≤ \frac{1}{2m+1}∥P_{2m+1}∥_{∞}2^{−(2m+1)j}.

We set g(t) = g_{2m}(t) = \frac{f(t)−D}{t} − ∑_{ℓ=0}^{2m} C_{ℓ}t^{ℓ} log t; under our assumptions on f, the function g is 2m times differentiable on [0, 1] and the (2m + 1)–st derivative is in L^{1}[0, 1]. Then we have

2^{−j} ∑_{k=1}^{2^{j}} g(\frac{k}{2^{j}} ) = ∫_{0}^{1} g(t) dt + \frac{1}{2}(g(1) − g(0))2^{−j} + ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{(2ℓ)!} (g^{(2ℓ−1)}(1) − g^{(2ℓ−1)}(0)) 2^{−2ℓj}
+ \frac{1}{(2m + 1)!}2^{−(2m+1)j} ∫_{0}^{1}P_{2m+1}(\{2^{j}x\})g^{(2m+1)}(x) dx  (17)

= ∫_{0}^{1} g(t) dt + \frac{1}{2}(g(1) − g(0))2^{−j} + ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{(2ℓ)!} (g^{(2ℓ−1)}(1) − g^{(2ℓ−1)}(0)) 2^{−2ℓj} + R′_{j}

with |R′_{j}| ≤ \frac{1}{(2m+1)!}∥P_{2m+1}∥_{∞}∥g^{(2m+1)}∥_{1}.

Finally, we compute the sums

2^{−j} ∑_{k=1}^{2^{j}} (\frac{k}{2^{j}} )^{r} log \frac{k}{2^{j}}  (18)

for r ∈ ℕ_{0} using the Euler-MacLaurin summation formula. For this purpose we first compute the sum

\begin{aligned}2^{−(s+1)j} ∑_{k=1}^{2^{j}} k^{s} & = \frac{1}{s + 1} + \frac{1}{2^{1+j}} + ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} \binom{s}{2ℓ − 1}2^{−2ℓj} + 2^{−js}ζ(−s) \\ & − 2^{−(2m+1)j}\binom{s}{2m + 1} ∫_{1}^{∞}P_{2m+1}(\{2^{j}x\})x^{s−2m−1} dx; \end{aligned}  (19)

here we have used the identity (cf. [7])

ζ(−s) = −\frac{1}{s + 1} + \frac{1}{2} − ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} \binom{s}{2ℓ − 1} + \binom{s}{2m + 1} ∫_{1}^{∞}P_{2m+1}(\{x\})x^{s−2m−1} dx,

which is valid for ℜs < 2m.

Differentiating (19) and setting s = r ∈ ℕ_{0} yields

2^{−j} ∑_{k=1}^{2^{j}} (\frac{k}{2^{j}} )^{r} log \frac{k}{2^{j}} = −\frac{1}{(r + 1)^{2}} + ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} \frac{d}{ds}\binom{s}{2ℓ − 1}|_{s=r}2^{−2ℓj}
+ j2^{−jr}ζ(−r) log 2 − 2^{−jr}ζ′(−r)  (20)

− 2^{−(2m+1)j} \frac{d}{ds}\binom{s}{2m + 1}|_{s=r} ∫_{1}^{∞}P_{2m+1}(\{2^{j}x\})x^{r−2m−1} dx;

here we have used that \binom{r}{2m+1} = 0 for r < 2m. We note also that ζ(−r) = −\frac{B_{r+1}}{r+1} for r ≥ 1 and ζ(0) = −\frac{1}{2}.

Finally, we observe that

\frac{d}{ds}\binom{s}{2ℓ − 1}|_{s=r} = \begin{cases}(−1)^{r} \frac{r!(2ℓ − r − 2)!}{(2ℓ − 1)!} & for r ≤ 2ℓ − 2 \\ \binom{r}{2ℓ − 1} ∑_{t=0}^{2ℓ−2} \frac{1}{r − t} & for r > 2ℓ − 2. \end{cases}

Inserting this into (20) and estimating the integral trivially yields

\begin{aligned}2^{−j} ∑_{k=1}^{2^{j}} (\frac{k}{2^{j}} )^{r} log \frac{k}{2^{j}} & = −\frac{1}{(r + 1)^{2}} + ∑_{ℓ=1}^{⌊ \frac{r+1}{2} ⌋} \frac{B_{2ℓ}}{2ℓ} \binom{r}{2ℓ − 1} ∑_{t=0}^{2ℓ−2} \frac{1}{r − t}2^{−2ℓj} \\ & + j2^{−jr}ζ(−r) log 2 − 2^{−jr}ζ′(−r) \\ & − (−1)^{r} ∑_{ℓ=⌊ \frac{r+3}{2} ⌋}^{m} \frac{r!(2ℓ − r − 2)!}{(2ℓ − 1)!} \frac{B_{2ℓ}}{2ℓ} 2^{−2ℓj} + R_{j,r} \end{aligned}  (21)

with |R_{j,r}| ≤ \frac{r!(2m−r−1)!}{(2m+1)!}2^{−(2m+1)j}∥P_{2m+1}∥_{∞}.

Extending the last sum (21) to m + 2 for r = 2m and putting everything together we obtain (the C_{0}j2^{−j} log 2–term in the fourth line is to compensate the difference between ζ(0) and B_{1})

∑_{k=1}^{2^{j}} \frac{1}{k}f(\frac{k}{2^{j}} ) = D(j log 2 + γ + \frac{1}{2^{j+1}} − ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{2ℓ} 2^{−2ℓj} + R_{j}) +

∫_{0}^{1} \frac{f(t) − D}{t} dt + \frac{1}{2}(g(1) − g(0))2^{−j} + ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{(2ℓ)!} (g^{(2ℓ−1)}(1) − g^{(2ℓ−1)}(0)) 2^{−2ℓj} + (22)

C_{0}j2^{−j} log 2 + ∑_{r=0}^{2m} C_{r}(∑_{ℓ=1}^{⌊ \frac{r}{2} ⌋} \frac{B_{2ℓ}}{2ℓ} \binom{r}{2ℓ − 1} ∑_{t=0}^{2ℓ−2} \frac{1}{r − t}2^{−2ℓj} + j2^{−j(r+1)} \frac{B_{r+1}}{r + 1} log 2 −

2^{−j(r+1)}ζ′(−r) − (−1)^{r} ∑_{ℓ=⌊ \frac{r+2}{2} ⌋}^{m} \frac{r!(2ℓ − r − 2)!}{(2ℓ − 1)!} \frac{B_{2ℓ}}{2ℓ} 2^{−2ℓj}) + R̃_{j}

with

|R̃_{j}| ≤ 2^{−(2m+1)j}∥P_{2m+1}∥_{∞} (\frac{D}{2m + 1} + \frac{1}{(2m + 1)!}∥g^{(2m+1)}∥_{1} + ∑_{r=0}^{2m−1} C_{r} \frac{r!(2m − r − 1)!}{(2m + 1)!})

+ C_{2m} (|ζ′(−2m)|2^{−(2m+1)j} + |B_{2m+2}|2^{−2j(m+1)} + \frac{∥P_{2m+3}∥}{2m + 1}2^{−j(2m+3)});

here we have used that

∫_{0}^{1} \frac{f(t) − D}{t} dt = ∫_{0}^{1} g(t) dt − ∑_{r=0}^{2m} \frac{C_{r}}{(r + 1)^{2}} .

For the function

f(t) = Φ(t) = \frac{(3 − t)(1 + t + t^{2})}{3(1 − t)^{2}} + \frac{2t log t}{(1 − t)^{3}}

we have D = 1 and C_{r} = (r + 1)(r + 2), and ∫_{0}^{1} \frac{f(t)−1}{t} dt = −\frac{11}{6}.

For a numerical approximation of (15) we split summation at J and replace the infinite part of the sum by the asymptotic estimate (22). For J = 10 and m = 10 this gives an error estimate of 2.152 · 10^{−45}. Thus we have

S_{1} = 0.75657 97214 59537 81423 01968 71433 28464 81778 24250 446 …

In a similar way we can treat the sum

S_{2} = ∑_{j≥0} ∑_{1≤k<2^{j}} \frac{1}{k}Ψ(\frac{k}{2^{j}} )

In this case D = 0 and ∫_{0}^{1} \frac{Ψ(x)}{x} dx = 0. For J = 8 and m = 10 we obtain an error estimate

of 2.0765 · 10^{−48}. Thus we have

S_{2} = 0.43942 55733 00328 10923 54579 37094 93117 34110 28053 …

7. Concluding remarks

The method for the numerical computation of Mellin integrals as described in section 6 can be easily generalized to integrals of the form

∫_{c−i∞}^{c+i∞}f(s)\frac{ζ(1 − s)}{A^{s} − 1} ds for A > 1,

where f(s) is a meromorphic function in the whole complex plane satisfying the following properties:

• f(s) = O(|s|^{−1−ε}) for some positive ε and | arg(−s)| < π

• f(s) has no poles left of a line ℜs = σ_{0}

• the sum over the residues Res f(s)x^{s} converges for 0 < x < 1. If A is not an integer one has to use a slightly changed version of the Euler-MacLaurin summation formula:

∑_{1≤k<A^{n}} g (\frac{k}{A^{n}} ) = A^{n} ∫_{0}^{1} g(x) dx − \frac{1}{2}g(0) + (\{A^{n}\} − \frac{1}{2}) g(1)

+ ∑_{ℓ=1}^{m} \frac{B_{2ℓ}}{(2ℓ)!} (g^{(2ℓ−1)}(1) − g^{(2ℓ−1)}(0)) A^{−(2ℓ−1)n}

+ \frac{1}{(2m + 1)!} ∫_{0}^{1} P_{2m+1}(\{A^{n}x\})g^{(2m+1)}(x) dx.

Again singularities of g have to be subtracted as shown in section 6.

Acknowledgment. We thank two anonymous referees and Hsien–Kuei Hwang for their valuable remarks.

References

[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, New York, 1965.

[2] G. Andrews, R. Askey, and R. Roy. Special Functions. Number 71 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1999.

[3] J. A. Fill, H. M. Mahmoud, and W. Szpankowski. On the distribution for the duration of a randomized leader election algorithm. Ann. Appl. Probab., 6:1260–1283, 1996.

[4] P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: finite differences and Rice’s integrals. Theor. Comput. Sci., 144(1–2):101–124, June 1995.

[5] P. Grabner and H. Prodinger. An asymptotic study of a recursion occurring in the analysis of an algorithm on broadcast communication. Inf. Process. Lett., 65:89–93, 1998.

[6] P. J. Grabner. Searching for losers. Random Structures and Algorithms, 4:99–110, 1993.

[7] A. Ivić. The Riemann Zeta-Function. J. Wiley, New York, 1985.

[8] S. Janson and W. Szpankowski. Analysis of an asymmetric leader election algorithm. Electron. J. Comb., 4:#R17, 17 pages, 1997.

[9] P. Mathys and P. Flajolet. Q–ary collision resolution algorithms in random access systems with free or blocked channel access. IEEE Transactions on Information Theory, IT-31(2):217–243, March 1985.

[10] N. Nielsen. Handbuch der Theorie der Gammafunktion. Teubner, Leipzig, 1906.

[11] H. Prodinger. How to select a loser. Discrete Math., 120:149–159, 1993.

[12] R. Sedgewick and P. Flajolet. Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, Massachusetts, 1996.

[13] S.-H. Shiau and C.-B. Yang. A fast maximum finding algorithm on broadcast communications. Inf. Process. Lett., 60:81–89, 1996.

[14] S.-H. Shiau and C.-B. Yang. A fast sorting algorithm and its generalization on broadcast communications. preprint, 18 pages, 2000.

[15] S.-H. Shiau and C.-B. Yang. Sorting algorithms on broadcast communications: Algorithm and fundamental analysis. in preparation, 2000.

[16] E. C. Titchmarsh. The Theory of Functions. Oxford University Press, 1939.

(P. Grabner) Institut für Mathematik A, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria

  E-mail address: grabner@weyl.math.tu-graz.ac.at

(H. Prodinger) The John Knopfmacher Centre for Applicable Analysis and Number Theory, Department of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

  E-mail address: helmut@gauss.cam.wits.ac.za