SUBBLOCK OCCURRENCES IN SIGNED DIGIT REPRESENTATIONS

PETER J. GRABNER^{†}, CLEMENS HEUBERGER^{‡}, AND HELMUT PRODINGER

Abstract. Signed digit representations with base q and digits −\frac{q}{2}, …, \frac{q}{2} (and uniqueness being enforced by applying a special rule which decides whether −q/2 or q/2 should be taken) are considered with respect to counting the occurrences of a given (contiguous) subblock of length r. The average number of occurrences amongst the numbers 0, …, n−1 turns out to be const · log_{q} n + δ(log_{q} n) + o(1), with a constant and a periodic function of period one depending on the given subblock; they are explicitly described. Furthermore, we use probabilistic techniques to prove a central limit theorem for the number of occurrences of a given subblock.

1. Introduction

If we write 10^{6} in binary we obtain 11110100001001000000. This word contains the (contiguous) substring 100 three times. In this paper we are concerned with counting occurrences of a given substring (or block) (like 100) in representations of numbers. Since this is typically somewhat erratic, we are interested in an average

\frac{1}{N} ∑_{0≤n<N}(number of occurrences of a given block w in the representation of n).

This is a generalisation of counting the frequency of digits.

For the instance of the q–ary representation of numbers this average was investigated by Kirschenhofer in [11]; the more exotic (q, d)–ary representation of numbers with base q and digits d, d + 1, …, d + q − 1 was treated in [12]. The technique in these papers was an extension of Delange’s method [3]. However, in [6] a novel method, based on the Mellin–Perron summation formula was introduced, and it was indicated how it works for such subblock counting problems. We will use this technique in the present paper. (A Delange type analysis would be feasible but very messy.)

Recently, Heuberger and Prodinger [10] have considered a symmetric system

n = ∑_{j=0}^{∞} ε_{j}q^{j}

Date: October 28, 2002.

1991 Mathematics Subject Classification. Primary:11K16 ; Secondary:11A63, 11M41.

Key words and phrases. Digit representation, subblock occurrence, Mellin-Perron formula.

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

‡ This author is supported by grant S8307-MAT of the Austrian Science Fund.

with an even base q and digits ε_{j} ∈ \{−\frac{q}{2}, …, \frac{q}{2}\}. Such a system is a priori redundant because of the existence of both ±\frac{q}{2} but can be made unique by the condition that |ε_{j}| = q/2 implies 0 ≤ sign(ε_{j})ε_{j+1} < q/2 (Equivalent conditions where discussed in [10]). We call this expansion the symmetric signed digit expansion of n and denote it by (… ε_{2}(n)ε_{1}(n)ε_{0}(n)). For q = 2, this system was already considered by Reitwiesner in a computer science context in [15].

In this paper we are addressing the subblock counting problem in such symmetric signed digit expansions.

Before we announce our principal findings, we need some notation.

If a block b = (b_{s}, …, b_{0}) is given, we denote its value by value(b) = ∑_{ℓ} b_{ℓ}q^{ℓ}.

We also use Iverson’s notation, popularized in [8]: [P] is defined to be 1 if condition P is true, and 0 otherwise. With this notation we can count the number of subblock occurrences of b in (the symmetric signed digit expansions of) n via

(1.1)  s_{b}(n) = ∑_{k=0}^{∞} [(ε_{k+r−1}(n), …, ε_{k}(n)) = b] .

We only consider admissible blocks b: these blocks represent the number value(b) in the symmetric signed digit expansion. For interest we note that there are

\frac{2 + q}{1 + q} q^{r} − \frac{1}{1 + q} (−1)^{r}

admissible blocks of length r; this was implicitly proved in [9].

We also use the decomposition of a real number x as x = ⌊x⌋ + {x} with the fractional part {x} satisfying 0 ≤ {x} < 1.

As said before, we are going to study the quantity

(1.2)  S_{b}(N) = ∑_{n<N} ∑_{k=0}^{∞} [(ε_{k+r−1}(n), …, ε_{k}(n)) = b] .

We will prove the following theorem.

Theorem 1. Let q ≥ 2 be an even integer and r ≥ 1. For an admissible block b = (b_{r−1}, …, b_{0}) with |b_{r−1}| < \frac{q}{2} and b ≠ 0^{r} the number of occurrences of the block b in the symmetric signed digit expansions of the positive integers less than N satisfies

(1.3)  S_{b}(N) = \frac{Q(b_{0})}{q^{r}(q + 1)}N log_{q} N + h_{0}(b)N + NH_{b}(log_{q} N) + o(N),

where

(1.4) Q(η) =q + \begin{cases}2 & for η = 0, \\ 0 & for η = ±\frac{q}{2}, \\ 1 & else, \end{cases}

H_{b}(x) = ∑_{k∈ℤ\{0}}h_{k}(b)e^{2kπix},

h_{k}(b) =\frac{log q}{2kπi(log q + 2kπi)}(ζ (\frac{2kπi}{log q}, [value(b) < 0] + q^{−r} value(b) + \frac{R_{min}(b_{0})}{q^{r}(q + 1)})

− ζ (\frac{2kπi}{log q}, [value(b) < 0] + q^{−r} value(b) + \frac{R_{max}(b_{0})}{q^{r}(q + 1)})) for k ≠ 0,

h_{0}(b) = log_{q} Γ ([value(b) < 0] + q^{−r} value(b) + \frac{R_{min}(b_{0})}{q^{r}(q + 1)})

− log_{q} Γ ([value(b) < 0] + q^{−r} value(b) + \frac{R_{max}(b_{0})}{q^{r}(q + 1)})

− \frac{Q(b_{0})}{q^{r}(q + 1)} (r + \frac{1}{2} + \frac{1}{log q} − \frac{1}{q + 1}) + \frac{1}{q^{r−1}(q + 1)},

(1.5) R_{min}(η) = − \frac{q}{2} − [(η − 1) mod q ≥ \frac{q}{2}] ,
(1.6) R_{max}(η) =\frac{q}{2} + [η mod q < \frac{q}{2}] .

The function H_{b}(x) is a periodic continuous function of period 1 and mean 0. As usual ζ(s, x) denotes the Hurwitz ζ-function.

Remark. The case of blocks b with most significant digit b_{r−1} = ±\frac{q}{2} can be reduced to Theorem 1 by using the following simple observation

S_{b}(N) = \begin{cases}∑_{η=− \frac{q}{2} +1}^{0} S_{ηb}(N) & for b_{r−1} = −\frac{q}{2}, \\ ∑_{η=0}^{\frac{q}{2} −1} S_{ηb}(N) & for b_{r−1} = \frac{q}{2}. \end{cases}

The main term in this case is \frac{1}{2} \frac{Q(b_{0})}{q^{r}(q+1)}N log_{q} N.

The instance r = 1 (counting digits) was discussed in [10], although without mentioning the periodic fluctuations in explicit form. Thuswaldner [17] has used Dirichlet series and the Mellin-Perron summation formula to exhibit this fluctuating behaviour in the case q = 2 and r = 1.

The limit distribution of digital functions of various kinds has been investigated by several authors. Especially, we mention the work of M. Drmota and J. Gajdosik [4] for local and central limit theorems for the sum-of-digits function with respect to recurrence based numeration systems. Furthermore, central limit theorems for digital functions in polynomial subsequences of the integers have been studied by N. L. Bassily and I. Katai [1, 2].

We will prove the following central limit theorem for s_{b}(n).

Theorem 2. Let s_{b}(n) denote the number of occurrences of the block b in the symmetric signed digit expansion of n defined in (1.1). Then s_{b} satisfies

(1.7) lim_{N→∞} \frac{1}{N} # \{n < N | s_{b}(n) < \frac{Q(b_{0})}{q^{r}(q + 1)} log_{q} N + x\sqrt{V_{b} log_{q} N}\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{− \frac{t^{2}}{2}} dt,

where

(1.8) V_{b} = \frac{Q(b_{0})}{q^{r}(q + 1)}(1 + 2 ∑_{t=1}^{r−1} [b_{t} = b_{0}, …, b_{r−1} = b_{r−1−t}] \frac{1}{q^{t}}

+ 2\frac{q}{q^{r}(q + 1)} (1 − \frac{Q(b_{0})}{q + 1}) − (2r − 1)\frac{Q(b_{0})}{q^{r}(q + 1)}).

2. Explicit formulæ

In [10] we were able to give an explicit formula for the k-th digit of the symmetric signed digit expansion of n. The problem in this section is to combine this information for each individual digit of a given admissible block b in a manageable way.

Theorem 5 of [10] asserts that the digits of the symmetric signed digit expansion can be computed by

(2.1)  ε_{k}(n) = ∑_{s=0}^{q^{2}−1} c_{s} ⌊\frac{n}{q^{k+2}} + ξ_{s}⌋ ,

where k ≥ 0 and

ξ_{s} := \frac{s(q + 1) + q/2 + [s mod q < q/2]}{q^{2}(q + 1)},

c_{s} := \begin{cases}−(q − 1) & if s mod q = q/2 − [⌊s/q⌋ ≥ q/2], \\ 1 & otherwise \end{cases}

for 0 ≤ s < q^{2}.

It will be convenient to extend (2.1) to arbitrary reals x (instead of the integer n) and arbitrary integers k. We now show that this indeed defines a digit expansion for every real x.

In the proof of Theorem 5 in [10], (2.1) has been rewritten to

ε_{k}(x) = ∑_{j=0}^{q−1} (⌊\frac{x}{q^{k+1}} + \frac{j}{q} + \frac{q/2 + [j < q/2]}{q(q + 1)}⌋ − q ⌊\frac{x}{q^{k+2}} + \frac{j}{q} + \frac{q/2 + [j < q/2]}{q(q + 1)}⌋) .

It is clear that ε_{k}(x) = 0 for sufficiently large k. Therefore, we obtain

∑_{k=−L}^{∞} ε_{k}(x)q^{k} = ∑_{j=0}^{q−1} q^{−L} ⌊xq^{L−1} + \frac{j}{q} + \frac{q/2 + [j < q/2]}{q(q + 1)}⌋ = x + O(q^{−L}).

This implies ∑_{k∈ℤ} ε_{k}(x)q^{k} = x for all x ∈ ℝ.

Furthermore, the proof of Theorem 5 in [10] shows that |ε_{k}(x)| ≤ \frac{q}{2} and that |ε_{k}(x)| = \frac{q}{2} implies 0 ≤ sign(ε_{k}(x))ε_{k+1}(x) ≤ \frac{q}{2} − 1.

We also state (2.1) in an alternative way:

Lemma 1. Let k ∈ ℤ, x ∈ ℝ and let ξ_{−1} := 0 and ξ_{q^{2}} := 1. Then the ξ_{ℓ} are increasing. Choose 0 ≤ s ≤ q^{2} such that

(2.2)  ξ_{s−1} ≤ \{\frac{x}{q^{k+2}} \} < ξ_{s}.

Write s = mq + j where 0 ≤ m and 0 ≤ j < q.

Then the kth digit ε_{k}(n) of n can be expressed as

(2.3)  ε_{k}(n) = ε_{0}(s) = \begin{cases}j & if j < q/2, \\ j − q & if j > q/2, \\ q/2 & if j = q/2 and m < q/2, \\ −q/2 & if j = q/2 and m ≥ q/2. \end{cases}

Proof. It can easily be checked that the ξ_{ℓ} are increasing. Since ∑_{ℓ=0}^{q^{2}−1} c_{ℓ} = 0 and since ξ_{ℓ} + ξ_{q^{2}−1−ℓ} = 1 for −1 ≤ ℓ ≤ q^{2}, we can rewrite (2.1) as

ε_{k}(x) = ∑_{ℓ=0}^{q^{2}−1} c_{ℓ} ⌊y + 1 − ξ_{q^{2}−1−ℓ}⌋ ,

where y = {xq^{−(k+2)}}. By the monotonicity of the ξ_{ℓ}, relation (2.2) implies ⌊y + 1 − ξ_{ℓ}⌋ = [ℓ ≤ s − 1]. Therefore, we have

ε_{k}(x) = ∑_{ℓ=0}^{s−1} c_{ℓ} = ∑_{t=0}^{m−1} ∑_{ℓ=0}^{q} c_{tq+ℓ} + ∑_{ℓ=0}^{j−1} c_{mq+ℓ}.

By definition, ∑_{ℓ=0}^{q} c_{tq+ℓ} = 0 for all 0 ≤ t ≤ q − 1. This implies that

ε_{k}(x) = ∑_{ℓ=0}^{j−1} c_{mq+ℓ} = j − q [j − 1 ≥ q/2 − [m ≥ q/2]] .

This proves the first equation in (2.3). The second equation in (2.3) is Lemma 3 in [10]. □

We will now find out how the block (ε_{k+r−1}(n), …, ε_{k}(n)) can be calculated from the knowledge of {n/q^{k+r+1}}. To this aim, we fix some r ≥ 1, k ≥ 0 and some 1 ≤ j ≤ q^{r+1}(q + 1). We consider an integer n such that

(2.4)  \{\frac{n}{q^{k+r+1}} \} ∈ [\frac{j − 1}{q^{r+1}(q + 1)}, \frac{j}{q^{r+1}(q + 1)}) .

This implies that

\frac{(j − 1)/q^{ℓ}}{q^{2}(q + 1)} ≤ \frac{n}{q^{k+ℓ+2}} − uq^{r−ℓ−1} < \frac{j/q^{ℓ}}{q^{2}(q + 1)}

for some integer u and all 0 ≤ ℓ ≤ r − 1. By Lemma 1, the digit ε_{k+ℓ}(n) depends on j and ℓ only, and not on n: If −1 ≤ s_{ℓ} ≤ q^{2} is chosen such that

ξ_{s_{ℓ}−1} ≤ \{\frac{j − 1}{q^{ℓ+2}(q + 1)}\} < ξ_{s_{ℓ}},

then

ε_{k+ℓ}(n) = ε_{0}(s_{ℓ}).

Using Lemma 1 once more, we get

(2.5)  ε_{k+ℓ}(n) = ε_{ℓ} (\frac{j − 1}{q + 1}) .

Therefore, we study the digit expansion of real numbers in more detail.

Lemma 2. For all x ∈ ℝ there exist unique u ∈ ℤ and v ∈ ℝ with x = u + v such that

(2.6)  −\frac{q/2 + [(ε_{0}(u) − 1) mod q ≥ q/2]}{q + 1} ≤ v < \frac{q/2 + [ε_{0}(u) mod q < q/2]}{q + 1}.

Furthermore ε_{ℓ}(x) = ε_{ℓ}(u) for ℓ ≥ 0.

Proof. Since

\frac{q/2 + [ε_{0}(u) mod q < q/2]}{q + 1} = 1 − \frac{q/2 + [(ε_{0}(u + 1) − 1) mod q ≥ q/2]}{q + 1}

existence and uniqueness of u and v follows.

We consider first the case ℓ = 0. By Lemma 1, there is some s with ε_{0}(u) = ε_{0}(s) and ξ_{s−1} ≤ {u/q^{2}} < ξ_{s}. We assume first 1 ≤ s < q^{2}. By definition, we have

(s − 1) + \frac{q/2 + [(s − 1) mod q < q/2]}{q + 1} ≤ u − mq^{2} < s + \frac{q/2 + [s mod q < q/2]}{q + 1}

for some integer m. Since u is an integer, we conclude that

(s − 1) + ⌈\frac{q/2 + [(s − 1) mod q < q/2]}{q + 1}⌉ ≤ u − mq^{2} ≤ s + ⌈\frac{q/2 + [s mod q < q/2]}{q + 1}⌉ − 1.

Since the values of the ceiling functions equal 1, we can rewrite this as

(2.7) ξ_{s−1} + \frac{q/2 + [(s − 1) mod q ≥ q/2]}{q^{2}(q + 1)} ≤ \frac{u}{q^{2}} − m ≤ ξ_{s} − \frac{q/2 + [s mod q < q/2]}{q^{2}(q + 1)}.

Combining this with (2.6) yields

ξ_{s−1} ≤ \frac{u + v}{q^{2}} − m < ξ_{s},

which is equivalent to ε_{0}(u + v) = ε_{0}(s) = ε_{0}(u).

For s = 0 and s = q^{2} we have to do some extra work. We only show what happens for s = 0: we still have the upper bound as in (2.7). Thus the only problem occurs, if \frac{u+v}{q^{2}} − m < 0. But then

ξ_{q^{2}} = 1 > \frac{u + v}{q^{2}} − m + 1 ≥ 1 − \frac{\frac{q}{2} + 1}{q^{2}(q + 1)} = ξ_{q^{2}−1}

by (2.6). This also implies ε_{0}(x) = ε_{0}(u) as requested.

In order to deal with ℓ ≥ 1 we consider

∑_{k≥0}(ε_{k}(x) − ε_{k}(u))q^{k} = v − ∑_{k<0} ε_{k}(x)q^{k}.

The left hand side is an integer which is divisible by q by the above discussion. The absolute value of the right hand side is at most

\frac{q/2 + 1}{q + 1} + \frac{q}{2} ∑_{k≥1} q^{−k} < 2 ≤ q,

which implies that both sides vanish. This means that ∑_{k≥0} ε_{k}(x)q^{k} = ∑_{k≥0} ε_{k}(u)q^{k}. Since both sides are symmetric signed digit expansions of the same integer, the digits have to be equal. □

3. Counting blocks

Let b = (b_{r−1}, …, b_{0}) be an admissible block. We want to count the number of occurrences of the block b as a subblock of the digit expansions of the integers 0, …, N − 1. In order to avoid technical problems arising from leading zeros we exclude the block b = 0^{r}. Furthermore, we can exclude blocks b with most significant digit b_{r−1} ∈ \{±\frac{q}{2}\}. This ensures that ε_{ℓ}(wq^{r} + value(b)) = b_{ℓ} for 0 ≤ ℓ ≤ r − 1 and w ∈ ℤ, because Algorithm 2 of [10] does not consider w when computing the first r digits in that case. For blocks starting with zeros, it makes sense to tacitly assume that any number has a sufficient number of leading zeros.

Let b, n ≥ 1 and k ≥ 0 be fixed. By (2.4) and (2.5), we have (ε_{k+r−1(n)}, …, ε_{k}(n)) = b if and only if

\{\frac{n}{q^{k+r+1}} \} ∈ ⋃_{j∈J(b)} [\frac{j − 1}{q^{r+1}(q + 1)}, \frac{j}{q^{r+1}(q + 1)}) ,

where

(3.1)  J(b) = \{1 ≤ j ≤ q^{r+1}(q + 1) : (ε_{r−1} (\frac{j − 1}{q + 1}) , …, ε_{0} (\frac{j − 1}{q + 1})) = b\} .

In order to describe the set J(b), we write j − 1 = (q + 1)u + R with R_{min}(ε_{0}(u)) ≤ R < R_{max}(ε_{0}(u)) with R_{min} and R_{max} defined in (1.5). Then by Lemma 2 we have ε_{ℓ}(\frac{j−1}{q+1}) = ε_{ℓ}(u) for ℓ ≥ 0 and can rewrite (3.1) as

J(b) = {j = (q + 1)u + R + 1 : u ∈ ℤ, 1 ≤ j ≤ q^{r+1}(q + 1),

R_{min}(ε_{0}(u)) ≤ R < R_{max}(ε_{0}(u)), and (ε_{r−1}(u), …, ε_{0}(u)) = b}.

Under our assumptions on the block b we can write the numbers u satisfying the last condition as u = wq^{r} + value(b) with w ∈ ℤ. Thus we arrive at

J(b) = {j = (q + 1)(wq^{r} + value(b)) + R + 1 : w ∈ ℤ, 1 ≤ j ≤ q^{r+1}(q + 1), and

R_{min}(b_{0}) ≤ R < R_{max}(b_{0})}.

Inserting the definition of j in the range given for j, we get the following condition on w:

− ⌊q^{−r} (value(b) + \frac{R}{q + 1})⌋ ≤ w < q − ⌊q^{−r} (value(b) + \frac{R}{q + 1})⌋ .

By (1.5) we have sign(value(b) + \frac{R}{q+1}) = sign value(b) ≠ 0 and therefore

0 < (sign value(b)) (value(b) + \frac{R}{q + 1}) < q^{r}.

Summing up this gives

⌊q^{−r} (value(b) + \frac{R}{q + 1})⌋ = − [value(b) < 0] .

Thus we reach the following explicit characterization:

Proposition 1. Let 0^{r} ≠ b an admissible block with |b_{r−1}| < q/2, n be a positive integer and k ≥ 0. Let

I_{b} := ⋃_{[value(b)<0]≤w<q+[value(b)<0]} ⋃_{R_{min}(b_{0})≤R<R_{max}(b_{0})}

[\frac{wq^{r}(q + 1) + (q + 1) value(b) + R}{q^{r+1}(q + 1)}, \frac{wq^{r}(q + 1) + (q + 1) value(b) + R + 1}{q^{r+1}(q + 1)}) .

Then ((ε_{k+r−1}(n), …, ε_{k}(n)) = b if and only if

\{\frac{n}{q^{k+r+1}} \} ∈ I_{b}.

We now study the sum (1.2). We denote the interval [\frac{j−1}{q^{r+1}(q+1)}, \frac{j}{q^{r+1}(q+1)}) by I_{j} and its characteristic function by 1_{I_{j}}. The above proposition shows that

(3.2)  S_{b}(N) = ∑_{w=[value(b)<0]}^{q+[value(b)<0]−1} ∑_{R=R_{min}(b_{0})}^{R_{max}(b_{0})−1} S_{wq^{r}(q+1)+(q+1) value(b)+R+1}(N),

where

(3.3)  S_{j}(N) = ∑_{n<N} ∑_{k=0}^{∞} 1_{I_{j}} (\{\frac{n}{q^{k+r+1}} \}) .

We note that (q + 1)(wq^{r} + value(b)) + R + 1 ≥ 2 by (1.5).

4. Dirichlet series

In this section, we study the asymptotic behaviour of the sum S_{j}(N) defined in (3.3), where 1 < j ≤ q^{r+1}(q + 1) using Dirichlet generating functions and the Mellin-Perron summation formula.

We rewrite S_{j}(N) as

(4.1)  S_{j}(N) = ∑_{n=1}^{N}(N − n) ∑_{k=0}^{∞} (1_{I_{j}}({nq^{−k−r−1}}) − 1_{I_{j}}({(n − 1)q^{−k−r−1}}))

using Abel summation. It is clear that the difference in (4.1) only takes values in {0, ±1}. We now discuss for which n the non-zero values are taken.

The first term in the difference equals 1, if

n ≡ u mod q^{k+r+1} for some u ∈ \{⌈\frac{(j − 1)q^{k}}{q + 1} ⌉ , …, ⌈\frac{jq^{k}}{q + 1}⌉ − 1\} .

Using a similar expression for the second term in the difference, we obtain

1_{I_{j}}({nq^{−k−r−1}}) − 1_{I_{j}}({(n − 1)q^{−k−r−1}}) =

[n ≡ ⌈\frac{(j − 1)q^{k}}{q + 1} ⌉ mod q^{k+r+1}] − [n ≡ ⌈\frac{jq^{k}}{q + 1}⌉ mod q^{k+r+1}] .

Now we can write the Dirichlet generating function of

∑_{k=0}^{∞} (1_{I_{j}}({nq^{−k−r−1}}) − 1_{I_{j}}({(n − 1)q^{−k−r−1}}))

as

(4.2) ∑_{n=1}^{∞} \frac{1}{n^{s}} ∑_{k=0}^{∞} (1_{I_{j}}(\{nq^{−k−r−1}\}) − 1_{I_{j}}(\{(n − 1)q^{−k−r−1}\}))

= ∑_{k=0}^{∞} ∑_{n=0}^{∞} \frac{1}{(q^{k+r+1}n + ⌈\frac{(j−1)q^{k}}{q+1} ⌉)^{s}} − ∑_{k=0}^{∞} ∑_{n=0}^{∞} \frac{1}{(q^{k+r+1}n + ⌈\frac{jq^{k}}{q+1}⌉)^{s}} .

It is clearly enough to study functions ψ_{j}(s) defined by

ψ_{j}(s) = ∑_{k=0}^{∞} ∑_{n=0}^{∞} \frac{1}{(q^{k+r+1}n + ⌈\frac{jq^{k}}{q+1}⌉)^{s}} = ∑_{n=1}^{∞} \frac{λ_{j}(n)}{n^{s}} = ∑_{n=1}^{∞} \frac{λ_{j}^{(0)}(n)}{n^{s}} + ∑_{n=1}^{∞} \frac{λ_{j}^{(1)}(n)}{n^{s}},

where λ_{j}^{(ℓ)}(n) denotes the contribution originating from the terms k ≡ ℓ mod 2 (ℓ = 0, 1) in the first sum. The splitting of the sum is motivated by

⌈\frac{jq^{k}}{q + 1}⌉ = \frac{jq^{k}}{q + 1} + \frac{j(−1)^{k+1} mod (q + 1)}{q + 1}.

This leads us to studying the functions

(4.3) ∑_{n=1}^{∞} \frac{λ_{j}^{(ℓ)}(n)}{(n − α_{j}^{(ℓ)})^{s}} = ∑_{\begin{matrix}k≥0 \\ k≡ℓ mod 2 \end{matrix}} ∑_{n=0}^{∞} \frac{1}{(q^{k+r+1}n + \frac{jq^{k}}{q+1})^{s}} = \frac{q^{−(r+ℓ−1)s}}{q^{2s} − 1} ζ (s, \frac{j}{(q + 1)q^{r+1}} ) ,

where α_{j}^{(ℓ)} = \frac{j(−1)^{ℓ+1} mod (q+1)}{q+1}.

We will use the Mellin-Perron summation formula (cf. [16]) in the form

(4.4)  ∑_{n<N}(N − n)a_{n} = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞}∑_{n=1}^{∞} \frac{a_{n}}{(n − α)^{s}} (N − α)^{s+1} \frac{ds}{s(s + 1)},

where 0 ≤ α < 1 and c is in the half-plane of absolute convergence of the Dirichlet series. In the sequel we will write ∫_{(c)} for the contour integral over the vertical line ℜs = c. The usefulness of this in the context of digital counting was described (for α = 0) in the survey [6] and in the slightly more general situation 0 ≤ α < 1 in [7]. Without this version with the parameter α, one could still proceed successfully, as in [17], but that would be considerably more cumbersome and less elegant.

Applying (4.4) to the two functions in (4.3) separately with the two values of α_{j}^{(ℓ)} we obtain

(4.5)  \begin{aligned}∑_{n<N}(N − n)λ_{j}(n) & = ∑_{n<N}(N − n)λ_{j}^{(0)}(n) + ∑_{n<N}(N − n)λ_{j}^{(1)}(n) \\ & = \frac{1}{2πi} ∫_{(2)} \frac{q^{−(r−1)s}}{q^{2s} − 1} ζ(s, β_{j})(N − α_{j}^{(0)})^{s+1} \frac{ds}{s(s + 1)} \\ & + \frac{1}{2πi} ∫_{(2)} \frac{q^{−rs}}{q^{2s} − 1}ζ(s, β_{j})(N − α_{j}^{(1)})^{s+1} \frac{ds}{s(s + 1)}, \end{aligned}

where β_{j} = \frac{j}{(q+1)q^{r+1}} We now notice that ζ(σ + it, α) = O(|t|^{\frac{1}{2} −σ}) for σ ≤ 0 (cf. [16]). Thus we can shift the line of integration to ℜs = −\frac{1}{4} by taking residues at the poles in s = 1 and s = \frac{kπi}{log q} =: χ_{k} into account to obtain (4.6)

∑_{n<N}(N − n)λ_{j}(n) = \frac{q^{−(r−1)}}{2(q^{2} − 1)}(N − α_{j}^{(0)})^{2} + \frac{q^{−r}}{2(q^{2} − 1)}(N − α_{j}^{(1)})^{2}

+ \frac{1 − 2β_{j}}{4} (N − α_{j}^{(0)}) log_{q}(N − α_{j}^{(0)}) + \frac{1 − 2β_{j}}{4} (N − α_{j}^{(1)}) log_{q}(N − α_{j}^{(1)})

− \frac{1 − 2β_{j}}{4} (r + \frac{1}{log q} ) (N − α_{j}^{(0)}) − \frac{1 − 2β_{j}}{4} (r + 1 + \frac{1}{log q} ) (N − α_{j}^{(1)})

+ \frac{1}{2 log q} ζ′(0, β_{j})(2N − α_{j}^{(0)} − α_{j}^{(1)})

+ (N − α_{j}^{(0)}) ∑_{k∈ℤ\\{0\}} \frac{(−1)^{k(r−1)}}{2 log q} \frac{ζ(χ_{k}, β_{j})}{χ_{k}(χ_{k} + 1)}(N − α_{j}^{(0)})^{χ_{k}}

+ (N − α_{j}^{(1)}) ∑_{k∈ℤ\\{0\}} \frac{(−1)^{kr}}{2 log q} \frac{ζ(χ_{k}, β_{j})}{χ_{k}(χ_{k} + 1)}(N − α_{j}^{(1)})^{χ_{k}}

+ \frac{1}{2πi} ∫_{(− \frac{1}{4} )} ⋯ ds + \frac{1}{2πi} ∫_{(− \frac{1}{4} )} ⋯ ds.

It is clear from the absolute convergence of the two integrals that they are bounded by O(N^{\frac{3}{4}} ).

Similarly to the cases studied in [6] and [7] the above integrals could be computed by writing \frac{1}{q^{2s}−1} as a geometric series and shifting the line of integration back to ℜs = 2. Since the resulting formulæ are highly unpleasant, we restrict ourselves to the two asymptotic main terms.

Thus we have

(4.7) ∑_{n<N}(N − n)λ_{j}(n) = \frac{1}{2} \frac{1}{q^{r}(q − 1)}N^{2} + (\frac{1}{2} − β_{j}) N log_{q} N

+ (log_{q} Γ(β_{j}) − \frac{1}{2} log_{q} 2π − (\frac{1}{2} − β_{j}) (\frac{1}{log q} + \frac{1}{2} + r) − \frac{qα_{j}^{(0)} + α_{j}^{(1)}}{q^{r}(q^{2} − 1)} ) N

+ N (F_{j}(log_{q} N) + F_{j}(log_{q} N + 1)) + O(log N) + O(Nω(F_{j}, \frac{1}{N} )),

where the periodic function F_{j} of period 2 is given by its absolutely convergent Fourier series

F_{j}(x) = ∑_{k∈ℤ\\{0\}} \frac{(−1)^{kr}}{2 log q} \frac{ζ(χ_{k}, β_{j})}{χ_{k}(χ_{k} + 1)}e^{kπix}

and ω(F_{j}, δ) denotes the modulus of continuity of F_{j}. Clearly, G_{j}(x) = F_{j}(x) + F_{j}(x + 1) is a periodic function of period 1 with Fourier series

G_{j}(x) = ∑_{k∈ℤ\\{0\}} \frac{1}{log q} \frac{ζ(χ_{2k}, β_{j})}{χ_{2k}(χ_{2k} + 1)}e^{2kπix}.

Putting everything together we obtain

(4.8)

S_{j}(N) = ∑_{n<N}(N − n)(λ_{j−1}(n) − λ_{j}(n))

=\frac{1}{(q + 1)q^{r+1}} N log_{q} N

+ (log_{q} \frac{Γ(β_{j−1})}{Γ(β_{j})} − \frac{1}{(q + 1)q^{r+1}} (\frac{1}{log q} + \frac{1}{2} + r) − \frac{1}{q^{r}(q + 1)^{2}}

+ \frac{q[j ≡ 1 mod (q + 1)] − [j ≡ 0 mod (q + 1)]}{q^{r}(q^{2} − 1)})N

+ N (G_{j−1}(log_{q} N) − G_{j}(log_{q} N)) + o(N).

In order to obtain an asymptotic expression for S_{b}(N) stated in Theorem 1 we have to combine the equations (3.2) and (4.8). For this purpose we need two identities:

∑_{w=0}^{q−1} log_{q} Γ (x + \frac{w}{q}) = \frac{q − 1}{2} log_{q} 2π + \frac{1}{2} − qx + log_{q} Γ(qx) for q ≥ 2 (cf. [13]),

∑_{w=0}^{q−1} ζ (s, \frac{w}{q} + x) = q^{s} ∑_{n=0}^{∞} ∑_{w=0}^{q−1} \frac{1}{(nq + w + qx)^{s}} = q^{s}ζ(s, qx) for x > 0.

Furthermore, we notice that [value(b) < 0] + q^{−r} value(b) + \frac{R_{min}(b_{0})}{q^{r}(q+1)} > 0. This yields (1.3).

5. A central limit theorem

In this section we will sketch a proof of Theorem 2.

We first construct a probability space (Kubilius model, cf. [5]), which will be used to approximate the values of s_{b}(n) by random variables. For this purpose we consider the infinite product space

Ω = \{−\frac{q}{2}, …, \frac{q}{2}\}^{ℕ_{0}}

equipped with a probability measure μ given on cylinder sets by

μ (\{(ω_{j})_{j≥0} | ω_{j} = a_{j} for j ≤ k − 1\}) = lim_{N→∞} \frac{1}{N} # \{n < N | ε_{k−1}(n) = a_{k−1}, …, ε_{0}(n) = a_{0}\} .

The limit exists, since the subsets of ℕ given by fixing a finite number of digits correspond to residue classes modulo a power of q by Proposition 1. From this fact it also follows that (for j_{0} < j_{1} < ⋯ < j_{s})

(5.1) \frac{1}{N} # \{n < N | ε_{j_{s}}(n) = a_{j_{s}}, …, ε_{j_{0}}(n) = a_{j_{0}}\} =

μ (\{(ω_{j})_{j≥0} | ω_{j_{s}} = a_{j_{s}}, …, ω_{j_{0}} = a_{j_{0}}\}) + O (\frac{q^{j_{s}}}{N} ) .

We define random variables

X_{k}(ω) = [(ω_{k+r−1}, …, ω_{k}) = b].

From the definition of μ and Proposition 1 it follows that

(5.2)  μ (X_{k} = 1) = \frac{Q(b_{0})}{q^{r}(q + 1)} + \frac{(−1)^{k}}{q^{k+r}} (1 − \frac{Q(b_{0})}{q + 1}) ,

which shows that the random variables X_{k} are not quite identically distributed. Furthermore, we compute the joint distribution of X_{k} and X_{k+t} for t > r:

(5.3) μ (X_{k} = 1 ∧ X_{k+t} = 1) =

μ (X_{k} = 1) (μ (X_{k+t} = 1) + \frac{(−1)^{t+r}}{q^{t}} (1 − \frac{(−1)^{k+r}}{q^{k+r}} ) (1 − \frac{Q(b_{0})}{q + 1})) ,

which shows that the random variables X_{k} and X_{k+t} are not independent. The probabilities in the case t ≤ r depend on the self-overlapping structure of b and can be computed using (5.2). The variance of ∑_{k=0}^{K} X_{k} can be computed

(5.4) 𝕍 (∑_{k=0}^{K} X_{k}) = K \frac{Q(b_{0})}{q^{r}(q + 1)}(1 + 2 ∑_{t=1}^{r−1} [b_{t} = b_{0}, …, b_{r−1} = b_{r−1−t}] \frac{1}{q^{t}}

+ 2\frac{q}{q^{r}(q + 1)} (1 − \frac{Q(b_{0})}{q + 1}) − (2r − 1)\frac{Q(b_{0})}{q^{r}(q + 1)}) + O(1) = V_{b}K + O(1).

Equation (5.3) shows that the random variables X_{k} are φ-mixing in the sense of [14] with φ(t) = O(q^{−t}). An application of [14, Theorem 1.2.3] yields the central limit theorem for X_{k}

(5.5)  lim_{K→∞} μ (∑_{k=0}^{K} X_{k} < \frac{Q(b_{0})}{q^{r}(q + 1)}K + x\sqrt{KV_{b}}) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{− \frac{t^{2}}{2}} dt.

For technical reasons we replace the function s_{b}(n) by

s̃_{b}(n) = ∑_{k≤log_{q} N−log^{\frac{1}{3}} N} [(ε_{k+r−1}(n), …, ε_{k}(n)) = b]

and notice that s_{b}(n) − s̃_{b}(n) = O(log^{\frac{1}{3}} N). From (5.1) it follows that the normalized moments of s̃_{b}(n) converge to the same limit as the corresponding moments of ∑_{k≤log_{q} N−log^{\frac{1}{3}} N} X_{k}. Since (5.5) holds the convergence of moments implies

lim_{N→∞} \frac{1}{N} # \{n < N | s̃_{b}(n) < \frac{Q(b_{0})}{q^{r}(q + 1)} log_{q} N + x\sqrt{V_{b} log_{q} N}\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{− \frac{t^{2}}{2}} dt

by the Fréchet-Shohat theorem (cf. [5, Lemma 1.43]).

Acknowledgement. The authors thank an anonymous referee for pointing out the possiblity to prove a central limit theorem.

References

[1] N. L. Bassily. Distribution of q-ary digits in some sequences of integers. Ann. Univ. Sci. Budapest. Sect. Comput., 14:13–22, 1994. Festschrift for the 50th birthday of Karl-Heinz Indlekofer.

[2] N. L. Bassily and I. Kátai. Distribution of the values of q-additive functions on polynomial sequences. Acta Math. Hungar., 68:353–361, 1995.

[3] H. Delange. Sur la fonction sommatoire de la fonction“somme des chiffres”. Enseignement Math. (2), 21(1):31–47, 1975.

[4] M. Drmota and J. Gajdosik. The distribution of the sum-of-digits function. J. Théor. Nombres Bordeaux, 10:17–32, 1998.

[5] P. D. T. A. Elliott. Probabilistic number theory. I, Mean-value theorems, volume 239 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York, 1979.

[6] Ph. Flajolet, P. J. Grabner, P. Kirschenhofer, H. Prodinger, and R. F. Tichy. Mellin transforms and asymptotics: digital sums. Theoret. Comput. Sci., 123:291–314, 1994.

[7] P. J. Grabner, P. Kirschenhofer, and H. Prodinger. The sum-of-digits function for complex bases. J. London Math. Soc. (2), 57(1):20–40, 1998.

[8] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics. A foundation for computer science. Addison-Wesley, second edition, 1994.

[9] C. Heuberger and H. Prodinger. Carry propagation in signed digit representations. Preprint. Available

at http://www.opt.math.tu-graz.ac.at/~cheub/publications/carry.ps.

[10] C. Heuberger and H. Prodinger. On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing, 66:377–393, 2001.

[11] P. Kirschenhofer. Subblock occurrences in the q-ary representation of n. SIAM J. Algebraic Discrete Methods, 4(2):231–236, 1983.

[12] P. Kirschenhofer and H. Prodinger. Subblock occurrences in positional number systems and Gray code representation. J. Inform. Optim. Sci., 5(1):29–42, 1984.

[13] W. Magnus, F. Oberhettinger, and R. P. Soni. Formulas and Theorems for the Special Functions of Mathematical Physics. Springer, Berlin, New York, 1966.

[14] W. Philipp. Mixing sequences of random variables and probabilistic number theory. Number 114 in Memoirs of the American Mathematical Society. American Mathematical Society, Providence, R. I., 1971.

[15] G. W. Reitwiesner. Binary arithmetic. In Advances in computers, volume 1, pages 231–308. Academic Press, New York, 1960.

[16] G. Tenenbaum. Introduction to analytic and probabilistic number theory. Cambridge University Press, Cambridge, 1995.

[17] J. M. Thuswaldner. Summatory functions of digital sums occurring in cryptography. Period. Math. Hungar., 38:111–130, 1999.

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

E-mail address: peter.grabner@tugraz.at

(C. Heuberger) Institut für Mathematik B, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria

E-mail address: clemens.heuberger@tugraz.at

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

E-mail address: helmut@staff.ms.wits.ac.za