A NOTE ON THE PARITY OF

THE SUM-OF-DIGITS FUNCTION

Peter J. Grabner

1. Introduction

Let for the following ν(n) be the binary sum-of-digits function, i.e.

ν (∑_{l=0}^{L} ε_{l}2^{l}) = ∑_{l=0}^{L} ε_{l}.

Newman [Ne] proved that

S(N) = ∑_{n<N}(−1)^{ν(3n)}

is always positive and of exact order of magnitude N^{log_{4} 3}. Coquet [Co] observed that

(1.1)  S(N) = N^{log_{4} 3}F (log_{4} N) + \frac{η(N)}{3},

where F (x) is a continuous, nowhere differentiable periodic function of period 1 (to speak of continuity makes sense, because the values log_{4} N are dense modulo 1) and η(N) only takes the values 0, ±1. He also gave the extreme values of the function F. In [FGKPT] the mean value of F was computed.

It is now natural to ask how the function

∑_{n<N}(−1)^{ν(pn)}

behaves for given odd p. Numerical studies show that for most values of p this function takes positive and negative values. The asymptotic behaviour like a power of N times a periodic function persists (cf. [GKS], [Gr]). In a concluding section we want to give some examples and state conjectures in this context.

We want to investigate

T (N) = ∑_{n<N}(−1)^{ν(5n)}

and will prove

Typeset by AMS-TEX 2 PETER J. GRABNER

The author is supported by the Austrian Science Foundation, Project Nr.P8274-PHY

Theorem 1. The function T (N) is positive for N > 0 and satisfies

(1.2)  T (N) = N^{α}Φ(log_{16} N) + \frac{η_{5}(N)}{5}

with a continuous nowhere differentiable periodic function Φ of period 1,

η_{5}(N) = \{ \begin{matrix}0 & for N even \\ (−1)^{ν(5N−1)} & for N odd, \end{matrix}

and α = \frac{log 5}{log 16}. The function Φ satisfies

0.83808514 … = Φ (log_{16} \frac{176}{15}) = \frac{7}{10} (\frac{15}{11})^{α} ≤ Φ(x)

≤ \frac{9}{10} (\frac{60}{13})^{α} = Φ (log_{16} \frac{52}{15}) = 2.18677074 …

and

∫_{0}^{1} Φ(x) dx = 5^{α−1} \frac{c_{1} + c_{2} + c_{3} + c_{4}}{Γ(α + 1) log 16} = 1.56205765115 …

with

c_{k} = ∫_{0}^{∞}(g_{k}(1)e^{−x} + ⋯ + g_{k}(15)e^{−15x}+

(1 + g_{k}(1)e^{−x} + ⋯ + g_{k}(15)e^{−15x} − 5) (G_{k}(e^{−16x}) − 1))x^{α−1}dx, where g_{k}(n) = e^{\frac{2knπi}{5}} (−1)^{ν(n)} and

G_{k}(z) = ∏_{m=0}^{∞} (1 + g_{k}(1)z^{16^{m}} + ⋯ + g_{k}(15)z^{15·16^{m}}) .

2. Proof of the Theorem

Let for the following ξ_{k} = exp(\frac{2kπi}{5}) for k = 0, …, 4. Then it is an immediate consequence of 16^{n} ≡ 1 mod 5 that

(2.1)  g_{k}(n) = ξ_{k}^{n}(−1)^{ν(n)}

satisfies

(2.2)  g_{k}(16n + b) = g_{k}(n)g_{k}(b) for 0 ≤ b ≤ 15.

This property is called “complete 16-multiplicativity” and immediately yields

(2.3)  g_{k} (∑_{l=0}^{L} a_{l}16^{l}) = ∏_{l=0}^{L} g_{k}(a_{l}).

Thus the value of g_{k}(n) only depends on the digit expansion of n to the base 16. Setting G_{k}(M) = ∑_{n<M} g_{k}(n) we have

(2.4)  T (N) = \frac{1}{5}G_{0}(5N) + \frac{1}{5} ∑_{k=1}^{4} G_{k}(5N) = \frac{η_{5}(N)}{5} + \frac{1}{5} ∑_{k=1}^{4} G_{k}(5N).

We will now investigate the asymptotic behaviour of G_{k}(M), k = 1, …, 4: Let M = ∑_{l=0}^{L} a_{l}16^{l} be the 16-adic expansion of M and set M_{p} = ∑_{l=p}^{L} a_{l}16^{l}. Then we have (2.5)

G_{k}(M) = ∑_{n<M_{L}} g_{k}(n) + ∑_{p=0}^{L−1} ∑_{n=M_{p+1}}^{M_{p}−1} g_{k}(n) = G_{k}(a_{L}16^{L}) + ∑_{p=0}^{L} g_{k}(M_{p+1})G_{k}(a_{p}16^{p}).

Thus we have reduced the problem to the computation of G_{k}(a16^{l}):

G_{k}(a16^{l}) = ∑_{ε<a} g_{k}(ε)G_{k}(16^{l}) = G_{k}(a)G_{k}(16)^{l}.

Notice that

(2.6)  G_{k}(16) = ∑_{n=0}^{15} ξ_{k}^{n}(−1)^{ν(n)} = ∏_{l=0}^{3} (1 − ξ_{k}^{2^{l}}) = 5.

This holds because 2 is a primitive root mod 5 and therefore the product can be rewritten as ∏_{l=1}^{4}(1 − ξ_{k}^{l}). (We will refer to this argument later in the concluding remarks.)

We rewrite (2.5)

(2.7)  G_{k}(M) = 5^{L} ∑_{p=0}^{L} 5^{p−L}G_{k}(a_{p}) ∏_{l=p+1}^{L} g_{k}(a_{l})

and set

(2.8)  φ_{k} (∑_{l=0}^{∞} a_{l}16^{−l}) = ∑_{l=0}^{∞} ∏_{p=0}^{l−1} g_{k}(a_{p})G_{k}(a_{l})5^{−l}.

Notice that these functions are well-defined and continuous (this is proved in a more general setting in [Gr]) and φ_{k}(1) = 1, φ_{k}(16) = 5.

Inserting the definition of φ_{k} into (2.7) yields

(2.9) G_{k}(M) = 5^{[log_{16} M]}φ_{k} (\frac{M}{16^{[log_{16} M]}} ) = M^{α}5^{−\{log_{16} M\}}φ_{k} (16^{\{log_{16} M\}}) ,

where [x] and {x} denote the integer and the fractional part of x as usual. We set now ψ_{k}(x) = φ_{k}(x)x^{−α} for 1 ≤ x ≤ 16 and observe that

Ψ(x) = \frac{1}{5} ∑_{k=1}^{4} ψ_{k}(x)

is a continuous function which can be continued periodically (with period 1). Then we have

T (N) = (5N)^{α}Ψ(5N) + \frac{η_{5}(N)}{5}.

and Φ(y) = 5^{α}Ψ(5 · 16^{y}).

In order to compute the extremal values of Φ we derive an explicit formula for φ(x) = \frac{1}{5} ∑_{k=1}^{4} φ_{k}(x). For this purpose we introduce some notations:

α_{1}(l, x) = #{p < l : a_{p} = 1 ∨ a_{p} = 11} α_{2}(l, x) = #{p < l : a_{p} = 2 ∨ a_{p} = 7} α_{3}(l, x) = #{p < l : a_{p} = 3} α_{4}(l, x) = #{p < l : a_{p} = 4 ∨ a_{p} = 14} α_{5}(l, x) = #{p < l : a_{p} = 6} α_{6}(l, x) = #{p < l : a_{p} = 8 ∨ a_{p} = 13} α_{7}(l, x) = #{p < l : a_{p} = 9} α_{8}(l, x) = #{p < l : a_{p} = 12}

for x = ∑_{p=0}^{∞} \frac{a_{p}}{16^{p}} (from now on we will omit the dependence on x)

A(l) = α_{1}(l) + 2α_{2}(l) + 3α_{3}(l) + 4α_{4}(l) + α_{5}(l) + 3α_{6}(l) + 4α_{7}(l) + 2α_{8}(l) B(l) = α_{1}(l) + α_{2}(l) + α_{4}(l) + α_{6}(l)

and

A(l) mod 5
d(a_{l}, A(l)) 0 1 2 3 4
0  0 0 0 0 0
1  \frac{4}{5} −\frac{1}{5} −\frac{1}{5} −\frac{1}{5} −\frac{1}{5}
2  1 0 0 0 −1
3 \frac{6}{5} \frac{1}{5} \frac{1}{5} −\frac{4}{5} −\frac{4}{5}
4  1 0 1 −1 −1
5 \frac{6}{5} −\frac{4}{5} \frac{6}{5} −\frac{4}{5} −\frac{4}{5}
6  2 −1 1 −1 −1
7 \frac{9}{5} −\frac{6}{5} \frac{4}{5} −\frac{6}{5} −\frac{1}{5}
8  2 −1 1 −2 0
9 \frac{11}{5} −\frac{4}{5} \frac{1}{5} −\frac{9}{5} \frac{1}{5}
10  2 0 0 −2 0
11  \frac{14}{5} −\frac{1}{5} −\frac{1}{5} −\frac{11}{5} −\frac{1}{5}
12  3 0 0 −2 −1
13  \frac{14}{5} −\frac{1}{5} −\frac{1}{5} −\frac{6}{5} −\frac{6}{5}
14  3 0 −1 −1 −1
15  \frac{16}{5} −\frac{4}{5} −\frac{4}{5} −\frac{4}{5} −\frac{4}{5}

We are now able to write

(2.10)  φ(x) = ∑_{l=0}^{∞}(−1)^{B(l)} \frac{d(a_{l}, A(l))}{5^{l}}.

Detailed investigation of the entries of d(a, A) yields \frac{7}{10} ≤ φ ≤ 4 and also estimates for φ(x), x ∈ [\frac{k}{16^{l}} , \frac{k+1}{16^{l}}], 16^{l} ≤ k < 16^{l+1}:

(2.11)  \begin{matrix}φ (\frac{k}{16^{l}} ) + (−1)^{B(l+1)}m(B(l + 1) + 1, A(l + 1))5^{−l−1} ≤ φ(x) ≤ \\ φ (\frac{k}{16^{l}} ) + (−1)^{B(l+1)}m(B(l + 1), A(l + 1))5^{−l−1}, \end{matrix}

where m(B, A) is given by

A(l) mod 5
m(B(l), A(l)) 0 1 2 3 4
0  0 −\frac{61}{50} −\frac{11}{10} −\frac{5}{2} −\frac{3}{2}
B(l) mod 2
1  4 \frac{1}{2}  \frac{3}{2}  \frac{1}{10}  \frac{11}{50}

Outside the interval [1, 2] it can be proved by trivial estimates that Ψ(x) < \frac{9}{10}(\frac{12}{13})^{α} =: M. The interval [1, 2] has to be splitted into several parts to prove that the maximum of Ψ is attained at x = \frac{13}{12}.

(1) 1 ≤ x ≤ \frac{17}{16}: φ(x) ≤ \frac{1061}{1250} and Ψ(x) < \frac{1061}{1250} < M.

(2) \frac{13}{12} − \frac{1}{3}16^{−k} ≤ x ≤ \frac{13}{12} − \frac{1}{3}16^{−k−1} for k ≥ 1: φ(x) ≤ \frac{9}{10} − 32 · 5^{−k−2} and Ψ(x) ≤ (\frac{9}{10} − 32 · 5^{−k−2})(\frac{13}{12} − \frac{1}{3}16^{−k})^{−α} < M.

(3) \frac{13}{12} ≤ x ≤ \frac{5}{4}: φ(x) ≤ \frac{9}{10} and Ψ(x) ≤ M

(4) \frac{5}{4} ≤ x ≤ \frac{21}{16}: φ(x) ≤ \frac{24}{25} and Ψ(x) < M

(5) \frac{21}{16} ≤ x ≤ \frac{23}{16}: in this interval some local extrema are attained which are only ∼ \frac{1}{100} smaller than M; therefore this interval has to be split into 32 intervals of length \frac{1}{256} to prove Ψ(x) < M.

(6) \frac{23}{16} ≤ x ≤ 2: φ(x) ≤ \frac{261}{250} and Ψ(x) ≤ \frac{261}{250}(\frac{16}{23})^{α} < M.

In order to prove that Ψ(x) ≥ \frac{7}{10}(\frac{3}{11})^{α} =: m we note first that outside of the interval [3, 4] this inequality can be obtained by trivial estimates. The interval [3, 4] again has to be split:

(1) 3 ≤ x ≤ \frac{11}{3}: φ(x) ≥ \frac{7}{10} and Ψ(x) ≥ m

(2) \frac{11}{3} + \frac{1}{3}16^{−k−1} ≤ x ≤ \frac{11}{3} + \frac{1}{3}16^{−k}: φ(x) ≥ \frac{7}{10} + 32 · 5^{−k−3} and Ψ(x) ≥ (\frac{7}{10} + 32 · 5^{−k−3})(\frac{11}{3} + \frac{1}{3}16^{−k})^{−α} > m.

(3) \frac{59}{16} ≤ x ≤ 4: φ(x) ≥ \frac{939}{1250} and Ψ(x) ≥ \frac{939}{1250\sqrt{5}} > m After rescaling this yields the extremal values stated in the theorem.

It is an immediate consequence of (2.11) that for every x ∈ [0, 1] and every l > 0 there exists a y with |x − y| ≤ 16^{−l}, such that |φ(x) − φ(y)| ≥ \frac{43}{50}5^{−l−1}. Thus φ is nowhere differentiable.

It remains to compute the mean value of Φ. For this purpose we note that in [Gr] a formula for the Fourier coefficients of a fractal function occurring in the context of q-multiplicative functions is developed. Inserting the 16-multiplicative functions g_{k} into this formula yields the mean value stated in the theorem. □

3. Concluding Remarks

In the recent paper [GKS] the asymptotic behaviour of the summatory function

∑_{n<N}(−1)^{ν(pn+q)}

for prime numbers p and 0 ≤ q < p is investigated. It turns out that for all these functions the asymptotic behaviour resembles that discussed in the previous section; however it seems to be difficult to determine the value of the exponent of N in the asymptotic formula, because it depends on the value

∑_{n<2^{s}} ζ^{n}(−1)^{ν(n)} = ∏_{k=0}^{s−1} (1 − ζ^{2^{k}}) ,

where ζ is a p-th root of unity and s is the multiplicative order of 2 mod p. In the cases s = p − 1 and s = \frac{p−1}{2} it is possible to derive general formulæ for this expression (cf. [GKS]).

The graph of Φ(x).

By an immediate generalization of the method used above it is possible to describe the behaviour of ∑_{n<N}(−1)^{ν(p^{r}n)}. The cases p = 3 and p = 5 are the easiest, because 2 is a primitive root mod 3^{r} and mod 5^{r}. Here the asymptotic behaviour of the summands of the formula corresponding to (2.4) depends on the order of the root exp(\frac{2kπi}{p^{r}}). The main term originates from the primitive 3^{rd} (5^{th} resp.) roots of unity. This gives asymptotic formulæ

S_{r}(N) = ∑_{n<N}(−1)^{ν(3^{r}n)} = \frac{1}{3^{r−1}} (3^{r}N)^{β}F (log_{4} 3^{r−1}N)

+ N^{\frac{β}{3}} F_{1} (\frac{1}{3} log_{4} N) + ⋯ + N^{\frac{β}{3^{r−1}}} F_{r−1} (\frac{1}{3^{r−1}} log_{4} N) + \frac{η_{3^{r}}(N)}{3^{r}}

T_{r}(N) = ∑_{n<N}(−1)^{ν(5^{r}n)} = \frac{1}{5^{r−1}} (5^{r}N)^{α}Φ (log_{16} 5^{r−1}N)

+ N^{\frac{α}{5}} Φ_{1} (\frac{1}{5} log_{16} N) + ⋯ + N^{\frac{β}{5^{r−1}}} Φ_{r−1} (\frac{1}{5^{r−1}} log_{16} N) + \frac{η_{5^{r}}(N)}{5^{r}},

where β = log_{4} 3 and F is the fractal function studied in Coquet’s paper [Co]; α = log_{16} 5 and Φ is the fractal function of Theorem 1 (this is the reason for the cumbersome notation of the two leading terms). The other functions occurring in the formulæ are also continuous and periodic of period 1, the η’s only take the values 0, ±1. Therefore these two sums only take at most finitely many negative values.

Let us conclude with some remarks on the sum U_{rs}(N) = ∑_{n<N}(−1)^{ν(3^{r}5^{s}n)}. The order of 2 mod 3^{r}5^{s} is 4 · 3^{r−1}5^{s−1}. Thus 2 generates half of ℤ_{3^{r}5^{s}}^{∗} and it is not too difficult to compute the possible values for the exponent: If ζ is a primitive 3^{k}5^{l}-th root of unity (0 < k ≤ r, 0 < l ≤ s) we have

P (ζ) = ∏_{t=0}^{4·3^{k−1}5^{l−1}} (1 − ζ^{2^{t}}) = ±1,

because P (ζ) = P (ζ̄) and P (ζ)P (ζ̄) = C_{3^{k}5^{l}}(1) = 1, where C_{q} is the cyclotomic polynomial of order q (these terms only contribute O(log N) to U_{rs}). Therefore the asymptotic behaviour of U_{rs}(N) is determined by those terms in the formula analogous to (2.4), which correspond to primitive 3^{k}-th and 5^{l}-th roots of unity. But these terms just constitute the sums S_{r} and T_{s}. This gives

U_{rs}(N) = \frac{1}{3^{r}5^{s}} (3^{r}S_{r}(5^{s}N) + 5^{s}T_{s}(3^{r}N)) + O(log N)

and again we have that U_{rs} only takes at most finitely many negative values. It remains as a question, for which primes p the sum ∑_{n<N}(−1)^{ν(pn)} is always positive. Numerical studies show that 17, 43 and 101 are possible candidates for this property, but this is far from a proof. The method used to prove this for p = 3 and p = 5 could be applied to p = 17, but would require immense computations for larger primes.

References

[Co] J. Coquet, A Summation Formula Related to the Binary Digits, Invent. math. 73 (1983), 107–115.

[FGKPT] P. Flajolet, P.J. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theor. Comput. Sci. (1993) (to appear).

[GKS] S. Goldstein, K.A. Kelly and E.S. Speer, The Fractal Structure of Rarefied Sums of the Thue-Morse Sequence, J. Number Th. 42 (1992), 1–19.

[Gr] P.J. Grabner, Completely q-Multiplicative Functions: the Mellin-Transform Approach, Acta Arith. (to appear).

[Ne] D.J. Newman, On the Number of Binary Digits in a Multiple of Three, Proc. A.M.S. 21 (1969), 719–721.

Institut für Mathematik A, Technische Universität Graz, Steyergasse 30, 8010 Graz, Austria

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