Raabe’s Identity and Covering Systems

Yevgenya Movshovich University of Illinois at Urbana-Champaign Urbana, IL 61801 USA yevgenya@illinois.edu

Abstract

A connection between covering systems and Bernoulli polynomials established by Fraenkel, Beebee, and Porubský asserts that a function ∑_{i=1}^{q} μ_{i}χ_{A_{i}}(k) is an M_{A}- covering function for a system of arithmetic sequences {A_{i}}_{i=1}^{q} if and only if it satisfies a generalized Raabe identity. The connection is used to derive recurrence formulas for the Bernoulli numbers. Here we show that the generalized Raabe identity is a sum of Raabe’s identities for A_{i} multiplied by μ_{i}, and this sum is the direct source of the above recurrence formulas. We show that many of these formulas are special cases of the original multiplication formula of Raabe. We find new applications of the connection to the covering systems.

1 Introduction

For a ∈ ℤ and n ∈ ℤ^{+} we let a(n) := a + nℤ = {x ∈ ℤ : x ≡ a (mod n)}. Here a(n) is called an arithmetic sequence (with common difference n) or a residue class (with modulus n). Consider a system A = {A_{1}, A_{2}, …, A_{q}} of arithmetic sequences

A_{i} = a_{i}(n_{i}) = a_{i} + n_{i}ℤ, 0 ≤ a_{i} < n_{i}, i = 1, …, q, q ≥ 1.  (1)

Definition 1. For i = 1, …, q, we let χ_{A_{i}}(k) denote the characteristic function of A_{i} and we let μ_{i} ≠ 0 be real numbers. An M_{A}-covering function for a system (1) is a sum

M_{A}(k) = ∑_{i=1}^{q} μ_{i}χ_{A_{i}}(k),  (2)

If all μ_{i} = 1, then M_{A}(k) is the usual covering function: w_{A}(k) = ∑_{i=1}^{q} χ_{A_{i}}(k).

Observe that the function M_{A}(k) is N_{A}-periodic with N_{A} = lcm(n_{1}, …, n_{q}). Definition 2. A system (1) is called a covering system or a cover (of ℤ) if w_{A} ≥ 1.

Paul Erdős introduced the concept of the covering system in the 1930s (see, e.g., [3]) and gave a nontrivial example of such a system: 0(2), 0(3), 1(4), 3(8), 7(12), 23(24). Definition 3. A system (1) is an exact M-cover if w_{A}(k) = M and an exact cover if M = 1. We also say that A is an exact M-cover of B if w_{A}(k) = Mw_{B}(k).

In what follows, (B_{m})_{m≥0} = (1, −\frac{1}{2}, \frac{1}{6}, 0, −\frac{1}{30}, 0, \frac{1}{42}, …) are the Bernoulli numbers and B_{m}(t) are the Bernoulli polynomials (8). In 1973 Fraenkel [6] found a connection between exact covers and B_{m}(t). Two years later Porubský [12] extended it to exact M-covers. Theorem 4 (A. Fraenkel, M = 1). A system of q ≥ 2 arithmetic sequences {a_{i}(n_{i})}_{i=1}^{q} is an exact M-cover if and only if

MB_{m} = ∑_{i=1}^{q} n_{i}^{m−1}B_{m}(\frac{a_{i}}{n_{i}} )  (3)

holds for every m ≥ 0.

Note that for m = 0, 1 the identity (3) gives us two well known properties of exact M-covers: ∑_{i=1}^{q} \frac{1}{n_{i}} = M (see also Corollary 8) and ∑_{i=1}^{q} \frac{a_{i}}{n_{i}} = \frac{q−M}{2} .

Beebee [1] observed that (3) is the case x = 0 of a more general identity (4). Theorem 5 (J. Beebee, M = 1). A system of q ≥ 2 arithmetic sequences {a_{i}(n_{i})}_{i=1}^{q} is an exact M-cover if and only if

MB_{m}(x) = ∑_{i=1}^{q} n_{i}^{m−1}B_{m}(\frac{x + a_{i}}{n_{i}} )  (4)

holds for every m ≥ 0.

Porubský [10, 12] used Beebee’s approach to extend Theorems 4 and 5 to a system (1) with an M_{A}-covering function (2) (and restrictions q ≥ 2, N = N_{A}, which we omit). Theorem 6 (Š. Porubský [10, Th. 1]). Let q, S ∈ ℤ^{+} and N = SN_{A}. Then (2) is an M_{A}(k)-covering function for the system (1) if and only if

N^{m−1} ∑_{k=0}^{N−1} M_{A}(k)B_{m}(\frac{x + k}{N} ) = ∑_{i=1}^{q} μ_{i}n_{i}^{m−1}B_{m}(\frac{x + a_{i}}{n_{i}} )  (5)

holds for every m ≥ 0.

We prove that, by itself, identity (5) is a sum of Raabe identities for arithmetics sequences a_{i}(n_{i}) (see Theorem 9 and Example 18). Aside from this result, our other contribution to Theorem 6 is proving its corollary, Theorem 10, where we take advantage of N = SN_{A} rather than N = N_{A}. Theorem 10 generalizes the results of Beebee and Fraenkel and is useful in applications to covering systems. In particular, it can be used to check if a system is an exact M-cover of another system (see Examples 20 and 21). In Section 4 we present Porubský’s proof of Theorem 6. In Theorem 16 of that section we derive identity (5) again, this time, from the asymptotic expansion of the Hurwitz zeta function. In Section 5 we give a few examples.

We begin the article by showing that many known identities for Bernoulli numbers, including those of Stern and Namias, are special cases of the multiplication formula proved by Raabe in his 1848 work “The Jacob Bernoulli function” [13].

2 Multiplication formula of J. L. Raabe (1848)

Raabe [13] proved his celebrated multiplication formula:

T^{m−1} ∑_{l=0}^{T −1} b_{m}(\frac{t + l}{T}) = b_{m}(t) − \frac{B_{m}}{m} (T^{m} − 1),  m ≥ 1,  (6)

for polynomials (t, \frac{t^{2}}{2} − \frac{t}{2}, \frac{t^{3}}{3} − \frac{t^{2}}{2} + \frac{t}{6}, …), called the Bernoulli functions in [13], ^{1}

b_{m}(t) = \frac{1}{m} ∑_{s=0}^{m−1} B_{s}\binom{m}{s}t^{m−s}.  (7)

Modern Bernoulli polynomials B_{m}(t) are linearly related to b_{m}(t), as follows:

B_{m}(t) = ∑_{s=0}^{m} B_{s} \binom{m}{s} t^{m−s} = m b_{m}(t) + B_{m}.  (8)

Polynomials b_{m}(t) are solutions to Jacob Bernoulli’s problem: find polynomials that sum

powers of consecutive integers ∑_{j=1}^{t−1} j^{m−1} = b_{m}(t) when m, t > 1 ( e.g., ∑_{j=1}^{30} j^{7} = b_{8}(31) ).

To prove (6), Raabe observed that for odd m the property b_{m}(1 − x) = (−1)^{m}b_{m}(x), written as a cancellation law b_{2n+1}(1 − x) + b_{2n+1}(x) = 0, yields b_{2n+1}(\frac{1}{2}) = 0 and a general cancellation law, that is, multiplication formula (6) at t = 0 and odd m ≥ 3:

b_{2n+1}(\frac{1}{T}) + b_{2n+1}(\frac{2}{T}) + ⋯ + b_{2n+1}(\frac{T −2}{T}) + b_{2n+1}(\frac{T −1}{T}) = 0.

1Raabe’s 1851 article [14] is often cited instead of his 1848 monograph [13] as the earliest place in the literature where the term Bernoulli polynomial (function) appears.

He then used impressive algebra to obtain (6) for all t and m.

Raabe’s identity (6) can be viewed as a recurrence relation for the Bernoulli numbers:

B_{m} = \frac{T^{m−1}}{1 − T^{m}} ∑_{l=0}^{T −1} b̂_{m}(\frac{t + l}{T}) − b̂_{m}(t),  (9)

where b̂_{m}(t) = m b_{m}(t), which are sometimes called Bernoulli polynomials of an older type. If we take t = 0 in the last identity, we see that it coincides with the following known identities: J. Stern [15], T = 2:

B_{m} = \frac{1}{2(1 − 2^{m})} ∑_{s=0}^{m−1} B_{s}\binom{m}{s}2^{s} ⇔^{(9)} B_{m} = \frac{2^{m−1}}{1 − 2^{m}} b̂_{m}(\frac{1}{2}).

V. Namias [9], T = 3:

B_{m} = \frac{1}{3(1 − 3^{m})} ∑_{s=0}^{m−1} B_{s}\binom{m}{s}3^{s}(1 + 2^{m−s}) ⇔^{(9)} B_{m} = \frac{3^{m−1}}{1 − 3^{m}} ∑_{l=0}^{2} b̂_{m}(\frac{l}{3}).

Namias [9] conjectured (and Deeba, Rodriguez [2] proved) that for arbitrary T

B_{m} = \frac{1}{T (1 − T^{m})} ∑_{s=0}^{m−1} T^{s} ∑_{l=1}^{T −1} B_{s}\binom{m}{s}l^{m−s} ⇔^{(9)} B_{m} = \frac{T^{m−1}}{1 − T^{m}} ∑_{l=0}^{T −1} b̂_{m}(\frac{l}{T} ).

In [1, 10] these identities (with our notation b̂_{m}(t) for the sum ∑_{s=0}^{m−1} B_{s}\binom{m}{s}t^{m−s} ) were cited as special cases of Fraenkel’s identity (3). The latter is the identity (5) in the recurrence form with t = 0 and M_{A}(k) = M:

B_{m}(M − ∑_{i=1}^{q} n_{i}^{m−1}) = ∑_{i=1}^{q} n_{i}^{m−1} b̂_{m}(\frac{a_{i}}{n_{i}} ).  (10)

3 Raabe’s identity for arithmetic sequences

When identity (5) (with N = T and x = t) is applied to the sequence 0(1) = ℤ, it becomes the multiplication formula (6) written in terms of modern Bernoulli polynomials (8):

T^{m−1} ∑_{l=0}^{T −1} B_{m}(\frac{t + l}{T}) = B_{m}(t).  (11)

A substitution t = \frac{x+a_{i}}{n_{i}} in (11) yields Raabe’s identity for an arithmetic sequence a_{i}(n_{i}):

T^{m−1} ∑_{l=0}^{T −1} B_{m} ( \frac{\frac{x+a_{i}}{n_{i}} + l}{T}) = B_{m} (\frac{x + a_{i}}{n_{i}} ).  (12)

Lemma 7. Let A_{i} = a_{i}(n_{i}), a_{i} < n_{i} and let T ∈ ℤ^{+}, N = T n_{i}, Then for any function f

∑_{k=0}^{N−1} χ_{A_{i}}(k)f(k) = ∑_{l=0}^{T −1} f(a_{i} + ln_{i}).

Proof. The set of integers {0, 1, 2, …, N − 1} is split into T subsets:

{0, 1, …, n_{i} − 1; n_{i}, …, 2n_{i} − 1; …; (T − 1)n_{i}, …, T n_{i} − 1}.

In each of these subsets there is exactly one member of A_{i}.

Corollary 8. Let (1) be a cover. Then Lemma 7 with f = 1 and N = SN_{A}, S ∈ ℤ^{+} yields

∑_{k=0}^{N−1} χ_{A_{i}}(k) = T = \frac{N}{n_{i}} . Thus \frac{1}{N} ∑_{k=0}^{N−1} w_{A}(k) = ∑_{i=1}^{q} \frac{1}{n_{i}} and ∑_{i=1}^{q} \frac{1}{n_{i}} ≥ 1.

Theorem 9. Identity (5) for a system A in (1) with an M_{A}-covering function (2) is the sum of q identities (12) multiplied by μ_{i}.

Proof. With f(k) = B_{m}(\frac{x+k}{N}) and N = T n_{i} in Lemma 7, Raabe’s identity (12) for a_{i}(n_{i}) admits the following form:

N^{m−1} ∑_{k=0}^{N−1} χ_{A_{i}}(k)B_{m} (\frac{x + k}{N} ) = n_{i}^{m−1}B_{m} (\frac{x + a_{i}}{n_{i}} ) .  (13)

Now if N = SN_{A}, then the sum of q identities (13) multiplied by μ_{i} is

∑_{i=1}^{q} μ_{i}N^{m−1} ∑_{k=0}^{N−1} χ_{A_{i}}(k)B_{m} (\frac{x + k}{N} ) = ∑_{i=1}^{q} μ_{i}n_{i}^{m−1}B_{m} (\frac{x + a_{i}}{n_{i}} ),  (14)

which becomes (5) after we change the order of summation in the left side of (14).

Theorem 10 (Corollary to Theorem 6). A covering system A = {a_{i}( n_{i})}_{i=1}^{q} is an exact M-cover of a covering system B = {h_{j}( r_{j})}_{j=1}^{p} if and only if

M ∑_{j=1}^{p} r_{j}^{m−1}B_{m} (\frac{x + h_{j}}{r_{j}} ) = ∑_{i=1}^{q} n_{i}^{m−1}B_{m} (\frac{x + a_{i}}{n_{i}} )  (15)

holds for every m ≥ 0.

Proof. Let N = lcm(n_{1}, …, n_{q}; r_{1}, …, r_{p}) = S_{1}N_{A} = S_{2}N_{B}. We write (5) for systems A and B. By the assumption, w_{A}(k) = Mw_{B}(k), i.e., the left side of (5) for A equals that for B multiplied by M. Hence, the right sides of (5) for A and B satisfy Eq. (15).

Theorem 11 (Special case of Theorem 10). A covering system A = {a_{i}( n_{i})}_{i=1}^{q} is an exact M-cover of an arithmetic sequence h(r) if and only if for every m ≥ 0:

Mr^{m−1}B_{m} (\frac{x + h}{r}) = ∑_{i=1}^{q} n_{i}^{m−1}B_{m} (\frac{x + a_{i}}{n_{i}} ).  (16)

Remark 12. Theorem 11 tells us that writing Raabe’s identity (12) for a_{i}(n_{i}) for all m ≥ 0 is equivalent to exactly covering a_{i}(n_{i}) by the system {(a_{i} + ln_{i})(n_{i}T), l = 0, …, T − 1}.

4 Proof of Theorem 6

Lemma 13. Let a function M(z) be N-periodic and a function g(z) satisfy ∑_{z=0}^{∞} |g(z)| < ∞.

Then the summation in the series ∑ M(z) g(z) can be rearranged as follows:

∑_{z=0}^{∞} M(z) g(z) = ∑_{k=0}^{N−1} ∑_{l=0}^{∞} M(k + lN)g(k + lN) = ∑_{k=0}^{N−1} M(k) ∑_{l=0}^{∞} g(k + lN).

Corollary 14. Let (2) be an M_{A}(k)-covering function for the system (1) and let N = SN_{A}, S ∈ ℤ^{+}. In addition, let |y| < 1. Then

∑_{k=0}^{N−1} M_{A}(k)\frac{y^{k}}{1 − y^{N}} = ∑_{i=1}^{q} μ_{i} \frac{y^{a_{i}}}{1 − y^{n_{i}}} .  (17)

Proof. Because M_{A}(z) is N-periodic, using geometric series expansions, the fact that a_{i} < n_{i}, and Lemma 13, we conclude that

∑_{i=1}^{q} μ_{i} \frac{y^{a_{i}}}{1 − y^{n_{i}}} = ∑_{i=1}^{q} μ_{i} ∑_{l=0}^{∞} y^{a_{i}+ln_{i}} = ∑_{i=1}^{q} μ_{i} ∑_{z=0}^{∞} χ_{A_{i}}(z) y^{z} = ∑_{z=0}^{∞} M_{A}(z) y^{z}  (18)

= ∑_{k=0}^{N−1} M_{A}(k) ∑_{l=0}^{∞} y^{k+lN} = ∑_{k=0}^{N−1} M_{A}(k)\frac{y^{k}}{1 − y^{N}} .  □

Corollary 15 (Š. Porubský [12]). Let N = SN_{A}, S ∈ ℤ^{+}. Then (2) is an M_{A}(k)-covering function for the system (1) if and only if Eq. (17) holds for any y with |y| < 1.

We recall Euler’s generating function of polynomials B_{m}(t):

\frac{se^{st}}{e^{s} − 1} = ∑_{m=0}^{∞} \frac{B_{m}(t)}{m!} s^{m}.  (19)

Proof of Theorem 6 (J. Beebee, Š. Porubský). (⇐): We assume that Eq. (5) holds for every m ≥ 0. As in [1, 10], we multiply (5) by s^{m}/m!

and sum the result over m:

∑_{k=0}^{N−1} M_{A}(k) ∑_{m=0}^{∞} \frac{(sN)^{m}}{N m!} B_{m}(\frac{x + k}{N} ) = ∑_{i=1}^{q} μ_{i} ∑_{m=0}^{∞} \frac{(sn_{i})^{m}}{n_{i} m!} B_{m}(\frac{x + a_{i}}{n_{i}} ).

By Eq. (19) this is equivalent to

∑_{k=0}^{N−1} M_{A}(k)\frac{(sN)}{N} \frac{e^{sN(x+k)/N}}{e^{sN} − 1} = ∑_{i=1}^{q} μ_{i} \frac{(sn_{i})}{n_{i}} \frac{e^{sn_{i}(x+a_{i})/n_{i}}}{e^{sn_{i}} − 1} ,

which, with e^{s} = y, becomes (17). Thus M_{A} satisfies (2) by Corollary 15.

(⇒): Let M_{A} satisfy Eq. (2). Starting with (17) we reverse steps in the above argument and obtain Eq. (5) for every m ≥ 0.

The authors of the proofs of Theorems 5 and 6 use the generating function of integers employed in (18) of Corollary 14 to Lemma 13 together with Euler’s generating function (19).

Next we derive identity (5) from the asymptotic expansion of the Hurwitz zeta function using just Lemma 13.

Theorem 16. Identity (5) holds for any system A in (1) with an M_{A}-covering function (2).

Proof. By Euler-Maclaurin summation (see, e.g., [5, Ex. 3, §467], where L + x = a) ^{2} the asymptotic series of an L-th tail of the Hurwitz zeta function at 2 in powers of 1/(L + x) is

∑_{l=0}^{∞} \frac{1}{(L + x + l)^{2}} ∼ ∑_{k=0}^{∞} \frac{(−1)^{k}B_{k}}{(L + x)^{k+1}} .  (20)

The asymptotic series composed with the converging series yields the series in powers of 1/L:

∑_{l=0}^{∞} \frac{1}{(L + x + l)^{2}} ∼ ∑_{k=0}^{∞} \frac{(−1)^{k}B_{k}}{(L + x)^{k+1}} = ∑_{k=0}^{∞} \frac{(−1)^{k}B_{k}}{L^{k+1}} ∑_{j=0}^{∞} \binom{k + j}{j}\frac{(−x)^{j}}{L^{j}}

=^{k+j=m} ∑_{m=0}^{∞} \frac{(−1)^{m}}{L^{m+1}} ∑_{k=0}^{m} B_{k} \binom{m}{m − k}x^{m−k} =^{(8)} ∑_{m=0}^{∞} \frac{(−1)^{m}}{L^{m+1}} B_{m}(x).  (21)

2Fichtenholtz [5] uses the notation β_{n} for the Bernoulli numbers and B_{n} for the absolute values of nonzero Bernoulli numbers. More precisely, (β_{n})_{n≥1} = ( − \frac{1}{2}, \frac{1}{6}, 0, −\frac{1}{30}, 0, \frac{1}{42}, …) and (B_{n})_{n≥1} = (\frac{1}{6}, \frac{1}{30}, \frac{1}{42}, \frac{1}{30}, \frac{5}{66}, …).

Let N = SN_{A}, S ∈ ℤ^{+}. Lemma 13 and Eq. (21) with L replaced by L/N and x by (x+k)/N give us

∑_{z=0}^{∞} \frac{M_{A}(z)}{(L + x + z)^{2}} = ∑_{k=0}^{N−1} M_{A}(k) ∑_{l=0}^{∞} \frac{1}{(L + x + k + lN)^{2}}  (22)

= ∑_{k=0}^{N−1} \frac{M_{A}(k)}{N^{2}} ∑_{l=0}^{∞} \frac{1}{(\frac{L}{N} + \frac{x+k}{N} + l)^{2}} ∼ ∑_{m=0}^{∞} \frac{(−1)^{m}}{L^{m+1}} ∑_{k=0}^{N−1} M_{A}(k)N^{m−1}B_{m}(\frac{x + k}{N} ).

Similarly, Eq. (21) with L replaced by L/n_{i} and x by (x + a_{i})/n_{i} gives us

∑_{z=0}^{∞} \frac{∑_{i=1}^{q} μ_{i}χ_{A_{i}}(z)}{(L + x + z)^{2}} = ∑_{i=1}^{q} μ_{i} ∑_{l=0}^{∞} \frac{1}{(L + x + a_{i} + ln_{i})^{2}}  (23)

= ∑_{i=1}^{q} \frac{μ_{i}}{n_{i}^{2}} ∑_{l=0}^{∞} \frac{1}{(\frac{L}{n^{i}} + \frac{x+a_{i}}{n_{i}} + l)^{2}} ∼ ∑_{m=0}^{∞} \frac{(−1)^{m}}{L^{m+1}} ∑_{i=1}^{q} μ_{i}n_{i}^{m−1}B_{m} (\frac{x + a_{i}}{n_{i}} ) .

Now Eqs. (22) and (23) yield Eq. (5), because the asymptotic series is unique.

We note that, unlike Theorem 6, steps in the last theorem cannot be reversed because functions can share asymptotic series.

We conclude the section with the famous proof of a relation for moduli of the exact covers found by Mirsky and Newman, and independently, by Davenport and Rado (see, e.g., [4]).

Theorem 17 (H. Davenport, L. Mirsky, D. Newman, R. Rado). Let a system (1) be an exact M-cover and let its moduli n_{i} satisfy 1 < n_{1} ≤ n_{2} ≤ ⋯ ≤ n_{q−1} ≤ n_{q}. Then n_{q−1} = n_{q}.

3

Proof. In Eq. (18) of Corollary 14 we take μ_{i} = 1, i = 1, …, q and M_{A}(z) = M to have

\frac{M}{1 − y} = ∑_{i=1}^{q−1} \frac{y^{a_{i}}}{1 − y^{n_{i}}} + \frac{y^{a_{q}}}{1 − y^{n_{q}}} .  (24)

The assumption that n_{q−1} < n_{q} would contradict Eq. (24) when y → e^{2πi/n_{q}}:

lim_{y→e^{2πi/nq}} (\frac{M}{1 − y} − ∑_{i=1}^{q−1} \frac{y^{a_{i}}}{1 − y^{n_{i}}} ) ≠ lim_{y→e^{2πi/nq}} \frac{y^{a_{q}}}{1 − y^{n_{q}}} = ∞.

3Further results for covering systems in this direction can be found in [7, 16] and in “Covering systems and periodic arithmetical functions” (a talk given by Z. W. Sun at UIUC on April 13, 2006).

5 Examples

Identity (5) in the recurrence form with t = 0 and M_{A}(k) = w_{A}(k) was given in [10, Cor. 1]:

B_{m} ∑_{i=1}^{q} (\frac{N^{m}}{n_{i}} − n_{i}^{m−1}) = ∑_{i=1}^{q} n_{i}^{m−1} b̂_{m}(\frac{a_{i}}{n_{i}} ) − N^{m−1} ∑_{k=0}^{N−1} w_{A}(k) b̂_{m}(\frac{k}{N} ).  (25)

The term ∑_{i=1}^{q} \frac{N}{n_{i}} in the left side of Eq. (25) replaced ∑_{k=0}^{N−1} w_{A}(k) (see Corollary 8).

Example 18. Identity (25) applied to the system A = {0(2), 0(3), 1(6), 5(6)} with N = 6 is

B_{m}(2^{m−1} + 3^{m−1} − 5 · 6^{m−1}) = 6^{m−1} ( b̂_{m}(\frac{2}{6}) + b̂_{m}(\frac{3}{6}) + b̂_{m}(\frac{4}{6})).  [10, Cor. 3]

Since b̂_{m}(t) = B_{m}(t) − B_{m}, the above identity is equivalent to

B_{m}(2^{m−1} + 3^{m−1} − 2 · 6^{m−1}) = 6^{m−1}(B_{m}(\frac{2}{6}) + B_{m}(\frac{3}{6}) + B_{m}(\frac{4}{6})).  (26)

The latter is the sum of Raabe identities (12) for 0(2) with T = \frac{6}{2} and for 0(3) with T = \frac{6}{3}:

6^{m−1}(B_{m} + B_{m}(\frac{2}{6}) + B_{m}(\frac{4}{6})) = 2^{m−1}B_{m} and 6^{m−1}(B_{m} + B_{m}(\frac{3}{6})) = 3^{m−1}B_{m}.

Note that in Theorem 9 identity (26) for A is a sum (14) of 4 identities (12), but identity (12) applied to the arithmetic sequence 1(6) or 5(6) yields just B_{m} = B_{m}.

Example 19. Nevertheless, we could apply Eq. (25) in the original form (5) to a system A′ related to A, for example, to find B_{m}(1/6) without knowledge of B_{m}(1/2) and B_{m}(1/3):

B_{m}(\frac{1}{6}) = B_{m}(1 − 2^{m−1})(1 − 3^{m−1})/(6^{m−1} 2).  (27)

According to Theorem 11, writing identities (26) is equivalent to covering 0(3) by {0(6), 3(6)} and 0(2) by {0(6), 2(6), 4(6)}. Clearly systems A′ ={0(6), 2(6), 4(6), 0(6), 3(6), 1(6), 5(6)} and A have the same covering function: w_{A}(k) = 2 if k ≡ 0 (mod 6) and w_{A}(k) = 1 otherwise. We apply Eq. (5) to A′ with M_{A′} = w_{A}, N = N_{A} = 6 and t = 0 to get

6^{m−1} ∑_{k=0}^{5} B_{m}(\frac{k}{6}) + 6^{m−1}B_{m}(0) = 2^{m−1}B_{m}(0) + 3^{m−1}B_{m}(0) + 6^{m−1}(B_{m}(\frac{1}{6}) + B_{m}(\frac{5}{6}))

and use B_{m}(\frac{5}{6}) = (−1)^{m}B_{m}(\frac{1}{6}) and Raabe’s identity 6^{m−1} ∑_{k=0}^{5} B_{m}(\frac{k}{6}) = B_{m} to prove Eq. (27).

The next two examples show how their exact covers were constructed.

Example 20. Choi constructed an exact 2-cover that is not the union of two exact covers: 1(2), 0(3), 1(3), 2(6), 0(10), 4(10), 6(10), 8(10), 2(15), 5(30), 11(30), 12(30), 22(30), 23(30), 29(30) (see, e.g., [10, p. 156]). To confirm that this system is an exact 2-cover, we split its sequences 0(3), 1(3), 2(15) into odd and even terms and show that the modified cover is the union of an exact 2-cover B ∪ C of the sequence 1(2) and an exact 2-cover D ∪ E of the sequence 0(2):

B = 1(2);  C = {1(6), 3(6), 5(30), 11(30), 17(30), 23(30), 29(30)};
D = {0(6), 2(6), 4(6)};  E = {0(10), 4(10), 6(10), 8(10), 2(30), 12(30), 22(30)}.

Since B and D are already exact covers of 1(2) and 0(2) respectively, we use Theorem 11 with M = 1, x = 0 to show that C and E are such covers.

First, in Theorem 11 we let the sequence h(r) be 1(2) and the system A be C. In that case, the right side of (16) in Theorem 11 is

6^{m−1}B_{m}(\frac{1}{6}) + 6^{m−1}B_{m}(\frac{3}{6}) + 6^{m−1}5^{m−1} ∑_{l=0}^{5−1} B_{m}(\frac{5 + 6l}{30})

= 6^{m−1}B_{m}(\frac{1}{6}) + 6^{m−1}B_{m}(\frac{3}{6}) + 6^{m−1}B_{m}(\frac{5}{6}) = 2^{m−1}B_{m}(\frac{1}{2}),

which is the left side of (16). We have applied Raabe’s identity (12) with T = 5, x = \frac{5}{6} to the sum in the first row and with T = 3, x = \frac{1}{2} in the second row.

Now, similarly, in Theorem 11 we take h(r) = 0(2), A = E and with the help of (12) confirm (16):

10^{m−1} ∑_{l=0,2,3,4} B_{m}(\frac{2l}{10}) + 10^{m−1}3^{m−1} ∑_{l=0}^{3−1} B_{m}(\frac{2 + 10l}{30}) = 10^{m−1} ∑_{l=0}^{5−1} B_{m}(\frac{l}{5}) = 2^{m−1}B_{m}(\frac{0}{2}).

Example 21. Show that a system F ∪ G = {2^{i−1}(2^{i})}_{i=1}^{f} ∪ {(j − 1)2^{f}(n2^{f})}_{j=1}^{n} is an exact cover. First, we use (11) with t = 0 and T = n to see that G is an exact cover of 0(2^{f}):

∑_{i=1}^{f}(2^{i})^{m−1}B_{m}(\frac{1}{2}) + (2^{f})^{m−1}n^{m−1} ∑_{l=0}^{n−1} B_{m}(\frac{l}{n})  (28)

= ∑_{i=1}^{f}(2^{i})^{m−1}B_{m}(\frac{1}{2}) + (2^{f})^{m−1}B_{m}(0).  (29)

Then we apply Theorem 11 repeatedly using (11) with t = 0 and T = 2 to see that 2^{f−1}(2^{f})∪ 0(2^{f}) is an exact cover of 0(2^{f−1}), etc.:

(29) = ∑_{i=1}^{f−1}(2^{i})^{m−1}B_{m}(\frac{1}{2}) + (2^{f−1})^{m−1}2^{m−1}(B_{m}(\frac{0}{2}) + B_{m}(\frac{1}{2}))

= ∑_{i=1}^{f−1}(2^{i})^{m−1}B_{m}(\frac{1}{2}) + (2^{f−1})^{m−1}B_{m}(\frac{0}{2}) = ⋯ = B_{m}(\frac{0}{2}) = B_{m}.

Note that (29) = B_{m} is B_{m}(\frac{1}{2}) ∑_{i=1}^{f}(2^{i})^{m−1} = B_{m}(1 − (2^{f})^{m−1}) which computes B_{m}(\frac{1}{2}). Now (28) = B_{m} with B_{m}(t) = b̂_{m}(t) + B_{m} is the relation given in [10, Cor. 4]. The latter was (10) applied to the system F ∪ G and multiplied by 2^{f+1}(2^{m−1} − 1).

When the covering function w_{A} of a system A is unknown or complicated, the identity (5) can still compute and estimate the averages of w_{A}(k), kw_{A}(k), … over N_{A}.

Example 22. For an odd n ≥ 3, the system F ∪ H = {2^{i−1}(2^{i})}_{i=1}^{n−1} ∪ {j2^{n−1}(n2^{j−1})}_{j=1}^{n} [16, Ex. 1, p. 4314] is an example of a distinct cover of ℤ (all n_{i} are different), ^{4} thus by the result of Davenport-Mirsky-Newman-Rado it is not an exact cover. To show that it covers ℤ, we take f = n − 1 and observe that 0(n2^{f}) = n2^{f}(n2^{f}) and, if 0 ≤ j ≤ f, the sequence j2^{f}(n2^{j−1}) covers the sequence j2^{f}(n2^{f}). Hence, system H = {j2^{n−1}(n2^{j−1})}_{j=1}^{n} covers system G = {(j − 1)2^{f}(n2^{f})}_{j=1}^{n} of Example 21, while system F is that of Example 21.

As in [16], Corollary 8 computes the arithmetic average of w_{F ∪H}(k) with N = N_{F ∪H} = 2^{n−1}n:

\frac{1}{N} ∑_{k=0}^{N−1} w_{F ∪H}(k) = ∑_{i=1}^{n−1} \frac{1}{2^{i}} + ∑_{j=1}^{n} \frac{1}{n2^{j−1}} = 1 + \frac{2^{n} − n − 1}{2^{n−1} n} < 1 + \frac{2}{n}.  (30)

It shows that for large n the system F ∪ H covers integers with fewer overlaps.

Note that the system H = {h_{j}(r_{j})}_{j=1}^{n} = {j2^{n−1}(n2^{j−1})}_{j=1}^{n} is not in the form of (1). In order to apply (5) with m ≥ 1 to the system F ∪ H, we define h′_{j} = h_{j} − k_{j}r_{j} with k_{j} so that 0 ≤ h′_{j} < r_{j}, j = 1, …, n and write H = {h′_{j}(r_{j})}_{j=1}^{n}, where h′_{n} = 0.

Identity (5) at m = 1 computes the arithmetic average of kw_{A}(k) for any system (1):

\frac{1}{N} ∑_{k=0}^{N−1} kw_{A}(k) = \frac{N}{2} ∑_{i=1}^{q} \frac{1}{n_{i}} + ∑_{i=1}^{q} \frac{a_{i}}{n_{i}} − \frac{q}{2}.  (31)

Now (31) and (30) estimate the arithmetic average of kw_{F ∪H}(k) for our system:

\frac{1}{N} ∑_{k=0}^{N−1} k w_{F ∪H}(k) = \frac{N}{2} ∑_{i=1}^{q} \frac{1}{n_{i}} + ∑_{i=1}^{n−1} \frac{1}{2} + ∑_{j=1}^{n} \frac{h′_{j}}{r_{j}} − \frac{2n − 1}{2} < \frac{N − 1}{2} + \frac{N}{n} .

For an exact cover this average would be \frac{N−1}{2}.

6 Acknowledgments

We thank Peter Andrews, Bruce Reznick, John Wetzel, Daniel Klovsky, and the referee for their help and valuable comments.

4Erdős-Selfridge Conjecture (See e.g., [8]). There are no distinct covers with all n_{1}, …, n_{q} odd and greater than one.

References

[1] J. Beebee, Bernoulli numbers and exact covering systems, Amer. Math. Monthly 99 (1992), 946–948.

[2] E. Y. Deeba and D. M. Rodriguez, Stirling’s series and Bernoulli numbers, Amer. Math. Monthly 98 (1991), 423–426.

[3] P. Erdős, On integers of the form 2^{k} + p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.

[4] P. Erdős, On a problem concerning covering systems, Mat. Lapok. 3 (1952), 122–128.

[5] G. M. Fichtenholz, Differential- und Integralrechnung II, VEB Deutscher Verlag der Wissenschaften, 1990.

[6] A. S. Fraenkel, A characterization of exactly covering systems, Discrete Math. 4 (1973), 359–366.

[7] S. Guo and Z. W. Sun, On odd covering systems, Adv. Appl. Math. 35 (2005), 182–187.

[8] R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1981.

[9] V. Namias, A simple derivation of Stirling’s asymptotic series, Amer. Math. Monthly 93 (1986), 25–29.

[10] Š. Porubský, Identities involving covering systems, Math.Slovaca 44 (1994), 153–162.

[11] Š. Porubský, On m-times covering systems, Acta Arith. 29 (1976), 159–169.

[12] Š. Porubský, Covering systems and generating functions, Acta Arith. 26 (1975), 223– 231.

[13] J. L. Raabe, Die Jacob Bernoullische Function, Druck und Verlag von Orell, Füssli und Comp., 1848.

[14] J. L. Raabe, Zurückführung einiger Summen und bestimmten Integrale auf die Jacob Bernoullische, J. Reine Angew. Math. 42 (1851), 348–367.

[15] J. Stern, Beiträge zur Theorie der Bernoullischen und Eulerschen Zahlen, Abh. Geselschaft Wiss. Göttingen 23 (1878), 1–44.

[16] Z. W. Sun, Covering the integers by arithmetic sequences. II, Trans. Amer. Math. Soc. 348 (1996), 4279–4320.

2010 Mathematics Subject Classification: Primary 11B25; Secondary 11B68, 11M35. Keywords: covering system and function, Bernoulli polynomial, multiplication formula.

(Concerned with sequences \underline{A027641} and \underline{A027642}.)

Received March 28 2019; revised versions received April 2 2019; January 31 2020; February 5 2020; February 11 2020. Published in Journal of Integer Sequences, February 20 2020.

Return to Journal of Integer Sequences home page.