PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

This PDF 1.5 document has been generated by ABBYY FineReader / , and has been sent on pdf-archive.com on 09/04/2018 at 03:55, from IP address 73.181.x.x. The current document download page has been viewed 110 times.
File size: 522 KB (12 pages).
Privacy: public file

Document preview

INFINITE PRODUCTS ASSOCIATED WITH COUNTING
BLOCKS IN BINARY STRINGS
J.-P. A L L O U C H E AND J. O. S H A L L I T

ABSTRACT

Let w be a string of zeros and ones, and let ajn) be the function which counts the number of (possibly
overlapping) occurrences of w in the binary expansion of n. We show that there exists an effectively
computable rational function bjn) such that

By setting X = — 1 and exponentiating, we recover previous results and also obtain some new ones; for
example,

Our work is a generalization
Mendes France, and the authors.

of previous

results of D. Woods, D. Robbins,

H. Cohen, M.

1. Introduction
Let sQ(n) denote the sum of the digits of the non-negative integer n when written
in base q. Woods and Robbins [9, 7] showed that
/*&gt;
(1)

2*

This formula was generalized by the second author to bases other than 2 using
methods of real analysis [8]. Later, the first author and H. Cohen found more general
results using Dirichlet series [1].
In a joint paper with Cohen and M. Mendes France [3] the author showed that

for J i n a suitable region of convergence, from which the results of Woods and
Robbins easily follow upon letting X = — 1 and q = 2.
In [3] it was also shown that

where u(n) is the Rudin-Shapiro function, which counts the number of occurrences
of '11' in the binary expansion of n. This formula naturally suggests the existence of
similar formulas corresponding to the counting of any binary string.

Received 13 July 1987; revised 18 October 1987 and 29 March 1988.
1980 Mathematics Subject Classification (1985 Revision) 05A15.
J. London Math. Soc. (2) 39 (1989) 193-204
7

JLM36

194

J.-P. ALLOUCHE AND J. O. SHALLIT

The existence of such formulas is the question we address in this paper. For any
finite non-empty block w of zeros and ones, we define aJn) as the number of
occurrences of w in the binary expansion of n. With this quantity we associate an
infinite series of the form

whose sum is also —\/{\—X).
This allows us to evaluate some novel infinite
products, as well as recover previous results.
2. Notation
Let w be a string or block of zeros and ones (that is, we(0+1)*). Let
v: (0+1)* -&gt; N be the map that assigns to w its value when interpreted in base 2; for
example y(0101) = 5. Let \w\ denote the length of w, that is, the number of symbols
in the string w.
Let w be non-empty and let aJn) count the number of (possibly overlapping)
occurrences of the block w in the binary expansion of n. For example, a n (15) = 3.
Some clarification is needed in the case where w starts with a zero; if w # (V, then in
evaluating ajri) we assume that the binary expansion of n starts with an arbitrarily
long prefix of zeros. Thus aQXQ{5) = 1, since we consider the binary expansion of 5 to
be 00... 00101. This definition of aJn) is appropriate for all cases except w = 0*; in
this case we use the binary expansion of n which starts with a 1. Thus aoo(4) = 1.
If w and z are strings, let a'w{z) count the number of (possibly overlapping)

occurrences of w in z. Note that here the string z is not extended with leading zeros.
Finally, we define
L(x) = l o g 2 ( - ^

3. Some infinite series
Our goal is to prove the result mentioned at the end of the introduction. First,
however, we will prove the following.
LEMMA 1. Let wbea non-empty string of zeros and ones and let aw(n) be as defined
above. Let g and h be integers. Then for all k^0, the series

aw(gn+h)-k

converges.
Proof. It suffices to prove that

y
T
aw(gn+h)-k
converges. But this is majorized by
2
aw(n)-h

thus it suffices to prove that this last series converges.

BLOCKS IN BINARY STRINGS

195

Let b = 2 N , let N be a positive integer, and let / be defined by b1'1 ^ TV ^ bl - 1 , so
that / &lt; 1 + (log TV/log b). We may suppose that / ^ k. Let us write sjn) for the
function which counts the number of occurrences of the 'digit' w when n is written
in base b. Then
, ,^

U

I

1=1

(6-1)'-'.

aw(n)-k

Now bound ( 6 - 1 ) ' - ' by (2&gt;-1)' and ( ! ) by ^ &lt; /*. Thus
S(N) =

£

1 &lt; (fc+1)/*(6-1)' ^ c t (log#)*# l0g( *- 1)/l0B *.

Now put
[0

otherwise.

We see that

W=

E 1= I a(n),

from which we get

and, using the bound determined above for S(n), this quantity tends to a finite limit
as N -» oo.
THEOREM

2.

Lef w t e a non-empty string of zeros and ones and
g

= 2'&quot;&quot;&quot;1,

h = Kw)/2J.

, /or a// A: ^ 0,
w)) = - 1 ,

where

(3)

the s u m is over n ^ 1 if w = (V and n ^ O o t h e r w i s e .

Proof

Note that we claim that the sum is — 1, independent of k. Since

Lemma 1 ensures convergence of these series.
The proof is divided into three cases: (I) w ends in a 1; (II) w ends in a 0 but
w = 0&gt;.
Case I, in which w ends in a 1. Let djk) be defined by

dJto= E
7-2

196

J.-P. ALLOUCHE AND J. O. SHALLIT

By writing n = gr + m, with r ^ 0 and 0 ^ m ^ g— 1, we see that
*•(*)= E

E

L(2gr + 2m+\).

aw(gr+m)-k

Similarly, if we let
aw(2n+l)-k

then
«„(*)= E

I

TO-O

L(2gr+2m+l).

r&gt;0
ow,(29r+2m+l)-fc

Now we claim that
l

if m = [v(w)/2\,

This is easy to see, since the binary expansion of 2gn + 2m +1 is the same as that for
gn + m, except that there is an extra 1-bit on the end. Hence if
aw(2gn + 2m + 1) &gt; aw(gn + m)
then the last M bits of 2g + 2m+l must coincide with the string w, and so
m = [v(w)/2\, since w ends in 1. Thus we see that all but one of the terms in the sums
for djk) and ejk) are identical, and hence, on recalling that h = [v(w)/2\,
(k)-eww( (k)=
dww(k)e

£

L(2gr + v(w))-

aw(gr+h)-k

£

L(2gr + v(w)).

(4)

aw(gr+h)-k-l

Now if we could show that djk) = ejk) for k &gt; 0, then it would follow from
equation (4) that the value of the sum

aw(gr+h)-k

is independent of k and hence equal to dw(0) — ew(0). In fact, we now show that

where
E

&gt;

I&quot;1

iffc = 0,
iffc &gt;\.

For we have

E L(«) = E L ( 2 &quot;) + E
aiw(n)-k

au,(2n)-*

Hence

a

(I(n)-L(2«))

L(2«+l) =

E W-

= (&quot;£») +

aw(n)-k

This completes the proof of case I.

L(2n+1).

i) = i

BLOCKS IN BINARY STRINGS

197

Case II, in which w ends in a 0, but w # 0*. First, we define functions dw and e'w
similar to those defined above:
d'w{k)=

Z

L(2n)

aw{n)-k

and

e'w(k)=

£

Following the method used for case I, we easily find that
d'w{k)-e'w{k)=

£

L(2gr + v(w))-

£

As before, we shall obtain the relation between djk) and e'Jk). We have

£
n^l
n M (»)-t

n^l
ou,(2n)-fc

n&gt;l
au,(2n+l)-fc

e'w{k)= £

L(2«) = (-£,)+

Hence

£

(L(n)-L(2n+\))

This completes the proof of case II.
Case III, /« which w = (V. This case is left to the reader.
This completes the proof of Theorem 2.

4. Some unusual power series
We now modify Theorem 2 to obtain some unusual power series.
THEOREM 3. Let w be a string of zeros and ones, and
g

= 2'&quot;&quot;&quot;1,

h = [v(w)/2\,

and let X be a complex number with \X\ &lt; 1. Then

£ Xa^on+h
where

^

the s u m is over n ~ ^ \ f o r w = (V and n ^ O o t h e r w i s e .

Proof

For \X\ &lt; 1, the series £ n 5 i 0 X&quot; is absolutely convergent, and the quantities

198

J.-P. ALLOUCHE AND J. O. SHALLIT

are all negative; thus we have

= £ A*

£

L(2g«+ »(

where we have used Theorem 2.
This result, although appealing, is unsatisfactory in two ways. First, the exponent
of X is aw(gn + h) instead of ajn). Second, in order to obtain the infinite products
mentioned in the introduction, we must show that Theorem 3 in fact holds for all
\X\ ^ 1, X # l. The first of these problems is corrected in this section, while the
question of convergence on the unit circle is addressed in the next section.
We now show how to modify Theorem 2 so that the summation is over all n with
aw(n) = k. To do this, we need the notion of a suffix of a string. Let x and y be two
Strings. Then we say x is a suffix of y if there exists a third string z such that y = zx.
Now we prove the following.
4. Let t be an integer with binary expansion t =
(A) Ifblb2...br
is not a suffix ofw, then

b1b2...brbr+l...bs.

LEMMA

n
a w (2 r n+u(6 1 .. .br))-k

n
aw(2r&quot;1n+v(b

(B) If, however, bxb2...br

is a suffix of w, then

n
aw(2rn+v{bl.. .br))-k

n
aw(2r~ln+v(bt..

.br))-k

n
o u ,(2 r &quot;'n+t)(E76 2 ... br_x))-k

where tx = v(b2b3...brbr+l...bs),
t2 = v(blbz...brbr+l...bs),
complement of the bit b; that is,0 = 1; 1 = 0.

and by b we mean the

Proof. Part (A) of the lemma can be left to the reader. To prove part (B), we start
with the summation

£
and break the sum into two parts, corresponding to n = 2m + b1 and n = 2m + bls
where bx is a single bit. We get
£
n
aw(2r~ln+v(bt...br))-k

L(2*-1n + f 1 ) =

£

L(2°m + t)

m
aM,(2rm+w(61...6r))-fc

+

£

L(2°m + t2).

m
awi2 m+v(blbi...bT))-k
r

Now b1b2...br is a suffix of w, so b1 b2...br cannot be a suffix of w. Thus we may

BLOCKS IN BINARY STRINGS

199
r 1

change the index of summation in the rightmost sum to aw(2 ~ m +
and the result follows.
LEMMA

5.

v(blb2...br_1)),

There is a rational function bw{n) such that for all k^ 0 we have

E Iog 2 (6») = - 1 .

(5)

n
aw(n)-k

(The summation is over n ^ 1 for w = 01 and n ^ 0 otherwise.) This function bw(n)
is effectively computable, and the degree dw of the numerator and denominator ofbjji)
SQtiS eS

fi

A &lt; 2 M-1

Proof. To prove the first statement, we start with Theorem 2 and successively
apply Lemma 4. At each step, we convert a sum over aw(2rn + x^) to either one or
two sums over aJT^n + xJ. Thus, after at most |w| - 1 stages (and a total of at most
2M-i invocations of Lemma 4), we will reduce the original sum (3) to a sum of sums
of the form (5), which can be combined in a single sum using the properties of the
logarithm. The degree dw of the numerator and denominator correspond to the
number of invocations of Lemma 4(B), and hence dw ^ 2H~X.
Let us give an example. For w = 1010, Theorem 2 shows that

a,010(8n+5)-fc

By successive applications of Lemma 4, we find that

a

ioio&lt;8n+5&gt;-fc

a

ioio&lt; n &gt;-*

Putting this all together, we conclude that, for all k ^ 0,

H(4n + 3)(8« + 6)(8« + 2)(16«+ll)J-

&quot;

a loio (n)-fc

It can be shown that m a x M &lt; I dw = O(x101); from this it easily follows
that the algorithm to calculate bJn) is actually a polynomial-time algorithm. For the
details, see [4].
COMMENT.

5. Behaviour on the unit circle
In this section, we examine the convergence of

Y

l )

(6)

on the unit circle. We will show that (6) converges uniformly on each radius of the unit
disc, with the exception of the radius lying on the positive real line.
It suffices to show uniform convergence for the series

200

J.-P. ALLOUCHE AND J. O. SHALLIT

For this, we follow the technique used previously in [3]. Write
UN) = TW(N,X)=

£

*•-&lt;&quot;&gt;

so that

W&gt;

=

TK{N+\)

=

y

x£&lt;s
n
N
&quot; ^ x ^ - x n(n+\)Thus it suffices to show that, for each ray from the origin to a point ( ^ 1) on the unit
circle, there exists a &lt; 1 such that
\TW(N,X)\ = O(N*)

(7)

uniformly in X on the ray.
We do this for w # 0*, leaving the case w = 0* to the reader. For w = 1, this easily
follows from the fact that
T1(2m,X) =
Thus let us assume that \w\ ^ 2. We write A = 2 N ~ 1 and define A different sums,
P0(m) to PA_x{m), by

Clearly at least one of the sums Pf(m) coincides with Tw(Am); if w = wx w2... wfc, we
may take

Thus to bound Tw(Am), it suffices to give an upper bound for
IIWIloO,
where the column vector P(m) is defined by

/ /»„(«) \
P(m)=[ \ ,
\PA-i(m)r
and the norm Hull^ is defined by

First, we observe that the vector P(m) can be written as a linear transformation
of the vector P(m— 1). Recall that a'w{z) counts the number of occurrences of the
string w in the string z. Then we have the following.
LEMMA

6. Let MW{X) be the AY, A matrix with
MW(X) = [My] = [A-&gt;^&gt;],

where y} and yt are strings such that viy^ =j, v(yt) = i, \y,\ = \yt\ = |w| — 1. Then
P(m) =

Mw(X)P(m-\).

BLOCKS IN BINARY STRINGS

201

Proof. We have
Q^n&lt;Am

_

y

y

xaw(A(Ak+jW)
^aw(Ak+j)+a'w(yiyi)

Thus to bound llPCm)!!^, it suffices to determine a good bound for the matrix
norm \\MW(X)\\X, where
Halloo = max L |M,,|.
LEMMA 7. (A) 77ie matrix MJX) contains at least one row all of ones.
(B) At least one row ofMw(X) is not identically 1. In every such row, there is at least
one element 1 and at least one element X.

Proof. (A) Write w = w1w2...wk.

Let

k-\
Then it is easily verified that w is not a substring of any string of the form y^y^, and
the result follows from the description of Lemma 6.
(B) To see that at least one row of MW(X) is not identically 1, let
i&quot; =

v(w2w3...wk).

Then in row i&quot;, any column j whose least significant bit is equal to vvx will contain a
non-1 entry.
An argument similar to (A), but for columns, shows that every row contains at
least one element 1.
Finally, let i be the index of a row of M = MW(X) that is not identically 1. Then
w must be a substring of some string of the form y}yv Choosey so that this substring
appears as far to the right as possible; then yjyi = xwz for some strings x and z. Then
either |JC| = 0, in which case Mi} = X, or \x\ = p &gt; 0. In this latter case, let
X'

=

P
Then w matches the string x'wz in exactly one place, and this string corresponds to
yryt for some value o f / ; that is, an element X in the rth row.
Now let us recall the basic facts about matrix norms [5]. Let M be a matrix. Let
o(M) be the set of all eigenvalues of M. The spectral radius of M, ra(M), is defined as
ra(M) = max \X\.
leo(M)

Define the matrix norm
where M* denotes the conjugate transpose.