Construction of Normal Numbers via Generalized Prime Power Sequences

M. G. Madritsch and R. F. Tichy Department for Analysis and Computational Number Theory Graz University of Technology A-8010 Graz Austria

                   madritsch@math.tugraz.at
                        tichy@tugraz.at

Dedicated to Jean-Paul Allouche on the occasion of his 60^{th} birthday

Abstract We construct normal numbers in base q by concatenating q-adic expansions of prime

powers ⌊αp^{θ}⌋ with α > 0 and θ > 1.

1 Introduction

Let q ≥ 2 be a fixed integer and σ = 0.a_{1}a_{2} … be the q-ary expansion of a real number σ with 0 < σ < 1. We write d_{1} ⋯ d_{ℓ} ∈ {0, 1, …, q − 1}^{ℓ} for a block of ℓ digits in the q-ary expansion. By N (σ; d_{1} ⋯ d_{ℓ}; N) we denote the number of occurrences of the block d_{1} ⋯ d_{ℓ} in the first N digits of the q-ary expansion of σ. We call σ normal to the base q if for every fixed ℓ ≥ 1

R_{N}(σ) = R_{N,ℓ}(σ) = sup_{d_{1}···d_{ℓ}} |\frac{1}{N} N (σ; d_{1} ⋯ d_{ℓ}; N) − \frac{1}{q^{ℓ}} | = o(1)

as N → ∞, where the supremum is taken over all blocks d_{1} ⋯ d_{ℓ} ∈ {0, 1, …, q − 1}^{ℓ}.

A slightly different, however equivalent definition of normal numbers is due to Borel [6] who also showed that almost all numbers are normal (with respect to the Lebesgue measure) to any base. However, despite their omnipresence among the reals, all numbers currently known to be normal are established by ad hoc constructions. In particular, we do not know whether given numbers, such as π, e, log 2 and \sqrt{2}, are normal.

In this paper we consider the construction of normal numbers in base q as concatenation of q-ary integer parts of certain functions. A first result was achieved by Champernowne [8], who showed that

0.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …

is normal in base 10. This construction can be easily generalized to any integer base q. Copeland and Erdös [9] proved that

0.2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 …

is normal in base 10.

This construction principle has been generalized in several directions. In particular, Dumont and Thomas [12] used transducers in order to rewrite the blocks of the expansion of a given normal number to produce another one. Such constructions using automata yield to q-automatic numbers, i.e., real numbers whose q-adic representation is a q-automatic sequence (cf. Allouche and Shallit [1]). By these means one can show that for instance the number

∑_{n≥0} 3^{−2^{n}}2^{−3^{2^{n}}}

is normal in base 2.

In the present paper we want to use another approach to generalize Champernowne’s construction of normal numbers. In particular, let f be any function and let [f(n)]_{q} denote the base q expansion of the integer part of f(n). Then define

σ_{q} = σ_{q}(f) = 0. ⌊f(1)⌋_{q} ⌊f(2)⌋_{q} ⌊f(3)⌋_{q} ⌊f(4)⌋_{q} ⌊f(5)⌋_{q} ⌊f(6)⌋_{q} …,  (1)

where the arguments run through all positive integers. Champernowne’s example corresponds to the choice f(x) = x in (1). Davenport and Erdös [10] considered the case where f(x) is an integer valued polynomial and showed that in this case the number σ_{q}(f) is normal. This construction was subsequently extended to polynomials over the rationals and over the reals by Schiffer [23] and Nakai and Shiokawa [21], who were both able to show that R_{N}(σ_{q}(f)) = O(1/ log N). This estimate is best possible, as proved by Schiffer [23]. Furthermore, Madritsch et al. [19] gave a construction for f being an entire function of bounded logarithmic order.

Nakai and Shiokawa [20] constructed a normal number by concatenating the integer part of a pseudo-polynomial sequence, i.e., a sequence (⌊p(n)⌋)_{n≥1} where

p(x) = α_{0}x^{θ_{0}} + α_{1}x^{θ_{1}} + ⋯ + α_{d}x^{θ_{d}}  (2)

with α_{0}, θ_{0}, …, α_{d}, θ_{d} ∈ ℝ, α_{0} > 0, θ_{0} > θ_{1} > ⋯ > θ_{d} > 0 and at least one θ_{i} ∉ ℤ.

This method of construction by concatenating function values is in strong connection with properties of q-additive functions. We call a function f strictly q-additive, if f(0) = 0 and the function operates only on the digits of the q-adic representation, i.e.,

f(n) = ∑_{h=0}^{ℓ} f(d_{h}) for n = ∑_{h=0}^{ℓ} d_{h}q^{h}.

A very simple example of a strictly q-additive function is the sum of digits function s_{q}, defined by

s_{q}(n) = ∑_{h=0}^{ℓ} d_{h} for n = ∑_{h=0}^{ℓ} d_{h}q^{h}.

Refining the methods of Nakai and Shiokawa the first author obtained the following result.

Theorem 1 ([18, Theorem 1.1]). Let q ≥ 2 be an integer and f be a strictly q-additive function. If p is a pseudo-polynomial as defined in (2), then there exists ε > 0 such that

∑_{n≤N} f (⌊p(n)⌋) = μ_{f}N log_{q}(p(N)) + NF (log_{q}(p(N))) + O (N^{1−ε}) ,  (3)

where

μ_{f} = \frac{1}{q} ∑_{d=0}^{q−1} f(d)

and F is a 1-periodic function depending only on f and p.

The aim of the present paper is to extend the above results to prime power sequences. Let f be a function and set

τ_{q} = τ_{q}(f) = 0. ⌊f(2)⌋_{q} ⌊f(3)⌋_{q} ⌊f(5)⌋_{q} ⌊f(7)⌋_{q} ⌊f(11)⌋_{q} ⌊f(13)⌋_{q} …,  (4)

where the arguments of f run through the sequence of primes.

Letting f be a polynomial with rational coefficients, Nakai and Shiokawa [22] could show that τ_{q}(f) is normal. Moreover, letting f be an entire function of bounded logarithmic order, Madritsch et al. [19] showed that R_{N}(τ_{q}(f)) = O(1/ log N).

At this point we want to mention the connection of normal numbers with uniform distribution. In particular, a number x ∈ [0, 1] is normal to base q if and only if the sequence {q^{n}x}_{n≥0} is uniformly distributed modulo 1 (cf. Drmota and Tichy [11]). Here {y} stands for the fractional part of y. Let us mention Kaufman [17] and Balog [4, 3], who investigated the distribution of the fractional part of \sqrt{p} and p^{θ} respectively. Harman [14] gave estimates for the discrepancy of the sequence \sqrt{p}. In his papers Schoissengeier [24, 25] connected the estimation of the discrepancy of αp^{θ} with zero free regions of the Riemann zeta function. This allowed Tolev [29] to consider the multidimensional variant of this problem as well as to provide an explicit estimate for the discrepancy. This result was improved for different special cases by Zhai [31]. Since the results above deal with the case of θ < 1 Baker and Kolesnik [2] extended these considerations to θ > 1 and provided an explicit upper bound for the discrepancy in this case. This result was improved by Cao and Zhai [7] for \frac{5}{3} < θ < 3. A multidimensional extension is due to Srinivasan and Tichy [27].

Combining the methods for proving uniform distribution mentioned above with a recent paper by Bergelson et al. [5] we want to extend the construction of Nakai and Shiokawa [20] to prime numbers. Our first main result is the following theorem.

Theorem 2. Let θ > 1 and α > 0. Then

R_{N}(τ_{q}(αx^{θ})) = O(1/ log N).

Remark 3. This estimate is best possible, as Schiffer [23] showed.

In our second main result we use the connection of this construction of normal numbers with the arithmetic mean of q-additive functions as described above. Known results in this area are due to Shiokawa [26], who was able to show the following theorem.

Theorem 4 ([26, Theorem]). We have

∑_{p≤x} s_{q}(p) = \frac{q − 1}{2} \frac{x}{log q} + O (x (\frac{log log x}{log x})^{\frac{1}{2}} ) ,

where the sum runs over the primes and the implicit O-constant may depend on q.

Similar results concerning the moments of the sum of digits function over primes have been established by Kátai [16]. An extension to Beurling primes is due to Heppner [15].

Let π(x) stand for the number of primes less than or equal to x. Adapting these ideas to our method we obtain the following theorem.

Theorem 5. Let θ > 1 and α > 0. Then

∑_{p≤N} s_{q}(⌊αp^{θ}⌋) = \frac{q − 1}{2}π(N) log_{q} N^{θ} + O(π(N)),

where the sum runs over the primes and the implicit O-constant may depend on q and θ.

Remark 6. With simple modifications Theorem 5 can be extended to completely q-additive functions replacing s_{q}.

The proof of the two theorems is divided in three parts. In the following section we rewrite both statements and state the central theorem, which combines them and which we prove in the rest of the paper. In Section 3 we present all the tools we need in the proof of the central theorem. Finally, in Section 4 we proof the theorem.

2 Preliminaries

Throughout the paper, an interval denotes a set

I = (α, β] = \{x : α < x ≤ β\} with β > α ≥ \frac{1}{2}.

We will often subdivide a interval into smaller ones. In particular we use the observation that if log(β/α) ≪ log N, then (α, β] is the union of, say, s intervals of the type (γ, γ_{1}] with s ≪ log N and γ_{1} ≤ 2γ. Given any complex function F on I, we have

|∑_{x∈I} F (x)| ≪ (log N) | ∑_{γ<x≤γ_{1}} F (x)| ,  (5)

for some such (γ, γ_{1}].

In the proof p will always denote a prime. We fix the block d_{1} ⋯ d_{ℓ} and write N (f(p)) for the number of occurrences of this block in the q-ary expansion of ⌊f(p)⌋. By ℓ(m) we denote the length of the q-ary expansion of an integer m.

In the first step we want to get rid of the blocks that may occur between two expansions. To this end we define an integer N by

∑_{p≤N−1} ℓ (⌊p^{θ}⌋) < L ≤ ∑_{p≤N} ℓ (⌊p^{θ}⌋) ,  (6)

where ∑ indicates that the sum runs over all primes. Thus we get that

L = ∑_{p≤N} ℓ(⌊p^{θ}⌋) + O(π(N)) + O(θ log_{q}(N))

= \frac{θ}{log q} N + O (\frac{N}{log N} ) .

(7)

Here we have used the prime number theorem in the form

π(x) = Li x + O (\frac{x}{(log x)^{G}} ) ,

where G is an arbitrary positive constant and

Li x = ∫_{2}^{x} \frac{dt}{log t}.

Let N (n; d_{1} ⋯ d_{ℓ}) be the number of occurrences of the block d_{1} ⋯ d_{ℓ} in the expansion of n. Since we have fixed the block d_{1} ⋯ d_{ℓ} we will write N (n) = N (n; d_{1} ⋯ d_{ℓ}) for short. Then (7) implies that

|N (τ_{q}(x^{θ}); d_{1} ⋯ d_{ℓ}; L) − ∑_{p≤N} N (p^{θ})| ≪ \frac{L}{log L}.  (8)

For the next step we collect all the values that have a certain length of expansion. Let j_{0} be a sufficiently large integer. Then for each integer j ≥ j_{0} we get that there exists an N_{j} such that

q^{j−2} ≤ f(N_{j}) < q^{j−1} ≤ f(N_{j} + 1) < q^{j}.

We note that this is possible since f asymptotically grows as its leading coefficient. This implies that

N_{j} ≍ q^{\frac{j}{β}} .

Furthermore for N ≥ q^{j_{0}} we set J to be the greatest length of the q-ary expansions of f(p) over the primes p ≤ N, i.e.,

J := max_{p≤N} ℓ(⌊f(p)⌋) = log_{q}(f(N)) + O(1) ≍ log N.  (9)

In the next step we want to perform the counting by adding the leading zeroes to the expansion of f(p). For N_{j−1} < p ≤ N_{j} we may write f(p) in q-ary expansion, i.e.,

f(p) = b_{j−1}q^{j−1} + b_{j−2}q^{j−2} + ⋯ + b_{1}q + b_{0} + b_{−1}q^{−1} + ….

Then we denote by N^{∗}(f(p)) the number of occurrences of the block d_{1}, …, d_{ℓ} in the string 0 ⋯ 0b_{j−1}b_{j−2} ⋯ b_{1}b_{0}, where we filled up the expansion with zeroes such that it has length J. The error of doing so can be estimated by

\begin{aligned}0 & ≤ ∑_{p≤N} N^{∗}(f(p)) − ∑_{p≤N} N (f(p)) \\ & ≤ ∑_{j=j_{0}+1}^{J−1}(J − j) (π(N_{j+1}) − π(N_{j})) + O(1) \\ & ≤ ∑_{j=j_{0}+2}^{J} π(N_{j}) + O(1) ≪ ∑_{j=j_{0}+2}^{J} \frac{q^{j/β}}{j} ≪ \frac{N}{log N} ≪ \frac{L}{log L}. \end{aligned}  (10)

In the following two sections we will estimate this sum of indicator functions in order to prove the following proposition.

Proposition 7. Let θ > 1 and α > 0. Then

∑_{p≤N} N^{∗} (⌊αp^{θ}⌋) = q^{−k}π(N) log_{q} N^{θ} + O (\frac{N}{log N} )  (11)

Proof of Theorem 2. We insert (11) into (8) and get the desired result.

Proof of Theorem 5. For this proof we have to rewrite the statement. In particular, we use that the sum of digits function counts the number of 1s, 2s, etc. and assigns weights to them, i.e.,

s_{q}(n) = ∑_{d=0}^{q−1} d · N (n; d).

Thus

∑_{p≤N} s_{q}(⌊p^{θ}⌋) = ∑_{p≤N} ∑_{d=0}^{q−1} d · N (p^{θ}) = ∑_{p≤N} ∑_{d=0}^{q−1} d · N^{∗}(p^{θ}) + O (\frac{N}{log N} )

= \frac{q − 1}{2}π(N) log_{q}(N^{θ}) + O (\frac{N}{log N} )

and the theorem follows.

3 Tools

In this section we want to present all the tools we need on the way of proof of Proposition 7. We start with an estimation which essentially goes back to Vinogradov. This will provide us with Fourier expansions for the indicator functions used in the proof. As usual, for a real number y, the expression e(y) denotes exp{2πiy}. Lemma 8 ([30, Lemma 12]). Let α, β, Δ be real numbers satisfying

0 < Δ < \frac{1}{2}, Δ ≤ β − α ≤ 1 − Δ.

Then there exists a periodic function ψ(x) with period 1, satisfying 1. ψ(x) = 1 in the interval α + \frac{1}{2}Δ ≤ x ≤ β − \frac{1}{2}Δ,

2. ψ(x) = 0 in the interval β + \frac{1}{2}Δ ≤ x ≤ 1 + α − \frac{1}{2}Δ,

3. 0 ≤ ψ(x) ≤ 1 in the remainder of the interval α − \frac{1}{2}Δ ≤ x ≤ 1 + α − \frac{1}{2}Δ,

4. ψ(x) has a Fourier series expansion of the form

ψ(x) = β − α + ∑_{\begin{matrix}ν=−∞ \\ ν≠0 \end{matrix}}^{∞} A(ν)e(νx),

where

|A(ν)| ≪ min (\frac{1}{ν}, β − α, \frac{1}{ν^{2}Δ}) .  (12)

After we have transformed the sums under consideration into exponential sums we want to split the interval by the following lemma. Lemma 9. Let I = (a, b] be an interval and F be a complex function defined on I. If log(b/a) ≪ L, then I is the union of ℓ intervals of the type (c, d] with ℓ ≪ L and d ≤ 2c. Furthermore we have

|∑_{n∈I} F (n)| ≪ L | ∑_{n∈(c,d]} F (n)| ,

for some such (c, d]. Proof. For i = 1, …, ℓ let I_{i} be the ℓ splitting intervals. Then

|∑_{n∈I} F (n)| = |∑_{i=1}^{ℓ} ∑_{n∈I_{i}} F (n)| ≤ ℓ max_{1≤i≤ℓ} |∑_{n∈I_{i}} F (n)| ≪ L |∑_{n∈I_{i}} F (n)|

We will apply the following lemma in order to estimate the occurring exponential sums provided that the coefficients are very small. This corresponds to the case of the most significant digits in the expansion.

Lemma 10 ([28, Lemma 4.19]). Let F (x) be a real function, k times differentiable, and satisfying |F^{(k)}(x)| ≥ λ > 0 throughout the interval [a, b]. Then

|∫_{a}^{b} e(F (x))dx| ≤ c(k)λ^{−1/k}.

A standard tool for estimating exponential sums over the primes is Vaughan’s identity. In order to apply this identity we have to rewrite the exponential sum into a normal one having von Mangoldt’s function as weights. Therefore let Λ denote von Mangoldt’s function, i.e.,

Λ(n) = \begin{cases}log p, & if n = p^{k} for some prime p and an integer k ≥ 1; \\ 0, & otherwise. \end{cases}

In the next step we may subdivide this weighted exponential sum into several sums of Type I and II. In particular, let P ≥ 2 and P_{1} ≤ 2P, then we define Type I and Type II sums by the expressions

∑_{X<x≤X_{1}} a_{x} ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}} f(xy) (Type I)  (13)

∑_{X<x≤X_{1}} a_{x} ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}}(log y)f(xy)

∑_{X<x≤X_{1}} a_{x} ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}} b_{y}f(xy) (Type II)  (14)

with X_{1} ≤ 2X, Y_{1} ≤ 2Y, |a_{x}| ≪ P^{ε}, |b_{y}| ≪ P^{ε} for every ε > 0 and

P ≪ XY ≪ P,

respectively. The following lemma provides the central tool for the subdivision of the weighted exponential sum.

Lemma 11 ([2, Lemma 1]). Let f(n) be a complex valued function and P ≥ 2, P_{1} ≤ 2P. Furthermore let U, V, and Z be positive numbers satisfying

2 ≤ U < V ≤ Z ≤ P,  (15)
U^{2} ≤ Z, 128UZ^{2} ≤ P_{1}, 2^{18}P_{1} ≤ V^{3}.  (16)

Then the sum

∑_{P ≤n≤P_{1}} Λ(n)f(n)

may be decomposed into ≪ (log P)^{6} sums, each of which is either a Type I sum with Y ≥ Z or a Type II sum with U ≤ Y ≤ V.

The next tool is an estimation for the exponential sum. After subdividing the weighted exponential sum we use Vinogradov’s method in order to estimate the occurring unweighted exponential sums.

Lemma 12 ([20, Lemma 6]). Let k, P and N be integers such that k ≥ 2, 2 ≤ N ≤ P. Let g(x) be real and have continuous derivatives up to the (k + 1)th order in [P + 1, P + N]; let 0 < λ < 1/(2c_{0}(k + 1)) and

λ ≤ \frac{g^{(k+1)}(x)}{(k + 1)!} ≤ c_{0}λ (P + 1 ≤ x ≤ P + N),

or the same for −g^{(k+1)}(x), and let

N^{−k−1+ρ} ≤ λ ≤ N^{−1}

with 0 < ρ ≤ k. Then

∑_{n=P +1}^{P +N} e(g(n)) ≪ N^{1−η},

where

η = \frac{ρ}{16(k + 1)L}, L = 1 + ⌊\frac{1}{4}k(k + 1) + kR⌋ , R = 1 + ⌊\frac{log (\frac{1}{ρ}k(k + 1)^{2})}{− log (1 − \frac{1}{k})}⌋ . (17)

4 Proof of Proposition 7

We will apply the estimates of the preceding sections in order to estimate the exponential sums occurring in the proof. We will proceed in four steps.

1. In the first step we use a method of Vinogradov [30] in order to rewrite the counting function into the estimation of exponential sums. Then we will distinguish two cases in the following two steps.

2. First we assume that we are interested in a block which occurs among the most significant digits. This corresponds to a very small coefficient in the exponential sum and we may use the method of van der Corput (cf. [13]).

3. For the blocks occurring among the least significant digits we apply Vaughan’s identity together with ideas from a recent paper by Bergelson et al. [5].

4. Finally we combine the estimates of the last two steps in order to end the proof.

In this proof, the letter p will always denote a prime and we set f(x) := αx^{θ} for short. Furthermore we set

δ := min (\frac{1}{4}, 1 − θ) .  (18)

4.1 Rewriting the sum

Throughout the rest of the paper we fix a block d_{1} ⋯ d_{ℓ}. In order to count the occurrences of this block in the q-ary expansion of ⌊f(p)⌋ (2 ≤ p ≤ P) we define the indicator function

I(t) = \begin{cases}1, & if ∑_{i=1}^{ℓ} d_{i}q^{−i} ≤ t − ⌊t⌋ < ∑_{i=1}^{ℓ} d_{i}q^{−i} + q^{−ℓ}; \\ 0, & otherwise; \end{cases}  (19)

which is a 1-periodic function. Indeed, we have

I(q^{−j}f(n)) = 1 ⟺ d_{1} ⋯ d_{ℓ} = b_{j−1} ⋯ b_{j−ℓ}.

Thus we can write our block counting function as follows

N^{∗}(f(p)) = ∑_{j=l}^{J} I (q^{−j}f(p)) .  (20)

Following Nakai and Shiokawa [20] we want to approximate I from above and from below by two 1-periodic functions having small Fourier coefficients. In particular, we set H = N^{δ/3} and

\begin{matrix}α_{−} = ∑_{λ=1}^{ℓ} d_{λ}q^{−λ} + (2H)^{−1}, β_{−} = ∑_{λ=1}^{ℓ} d_{λ}q^{−λ} + q^{−ℓ} − (2H)^{−1}, Δ_{−} = H^{−1}, \\ α_{+} = ∑_{λ=1}^{ℓ} d_{λ}q^{−λ} − (2H)^{−1}, β_{+} = ∑_{λ=1}^{ℓ} d_{λ}q^{−λ} + q^{−ℓ} + (2H)^{−1}, Δ_{+} = H^{−1}. \end{matrix} (21)

We apply Lemma 8 with (α, β, δ) = (α_{−}, β_{−}, δ_{−}) and (α, β, δ) = (α_{+}, β_{+}, δ_{+}), respectively, in order to get two functions I_{−} and I_{+}. By the choices of (α_{±}, β_{±}, δ_{±}) it is immediate that

I_{−}(t) ≤ I(t) ≤ I_{+}(t) (t ∈ ℝ).  (22)

Lemma 8 also implies that these two functions have Fourier expansions

I_{±}(t) = q^{−ℓ} ± H^{−1} + ∑_{\begin{matrix}ν=−∞ \\ ν≠0 \end{matrix}}^{∞} A_{±}(ν)e(νt)  (23)

satisfying

|A_{±}(ν)| ≪ min(|ν|^{−1} , H |ν|^{−2}).

In a next step we want to replace I by I_{+} in (20). For this purpose we observe, using (22), that

|I(t) − I_{+}(t)| ≤ |I_{+}(t) − I_{−}(t)| ≪ H^{−1} + ∑_{\begin{matrix}ν=−∞ \\ ν≠0 \end{matrix}}^{∞} A_{±}(ν)e(νt).

Thus subtracting yields the main part, and summing over p ≤ N gives

|∑_{p≤N} I(q^{−j}f(p)) − \frac{π(N)}{q^{ℓ}} | ≪ π(N)H^{−1} + ∑_{\begin{matrix}ν=−∞ \\ ν≠0 \end{matrix}}^{∞} A_{±}(ν) ∑_{p≤N} e (\frac{ν}{q^{j}} f(p)) .  (24)

Now we consider the coefficients A_{±}(ν). Noting (12) one observes that

A_{±}(ν) ≪ \begin{cases}ν^{−1}, & for |ν| ≤ H; \\ Hν^{−2}, & for |ν| > H. \end{cases}

Estimating all summands with |ν| > H trivially we get

∑_{\begin{matrix}ν=−∞ \\ ν≠0 \end{matrix}}^{∞} A_{±}(ν)e (\frac{ν}{q^{j}} f(p)) ≪ ∑_{ν=1}^{H} ν^{−1}e (\frac{ν}{q^{j}} f(p)) + H^{−1}.

Using this in (24) yields

|∑_{p≤N} I(q^{−j}f(p)) − \frac{π(N)}{q^{ℓ}} | ≪ π(N)H^{−1} + ∑_{ν=1}^{H} ν^{−1} ∑_{p≤N} e (\frac{ν}{q^{j}} f(p)) .  (25)

Finally we sum over all js and get

|∑_{p≤N} N^{∗}(f(p)) − \frac{π(N)}{q^{ℓ}}J| ≪ π(N)H^{−1}J + ∑_{j=ℓ}^{J} ∑_{ν=1}^{H} ν^{−1}S(N, j, ν),  (26)

where we have set

S(N, j, ν) := ∑_{p≤N} e (\frac{ν}{q^{j}} f(p)) .

The crucial part is the estimation of the exponential sums over the primes. In the following we will distinguish two cases according to the size of j. This corresponds to the position in the expansion of f(p). In particular, let ρ > 0 be arbitrarily small then we want to distinguish between the most significant digits and the least significant digits, i.e., between the ranges

1 ≤ q^{j} ≤ N^{θ−1+ρ} and N^{θ−1+ρ} < q^{j} ≤ N^{θ}.

4.2 Most significant digits

In this subsection we assume that

N^{θ−1+ρ} < q^{j} ≤ N^{θ},

which means that we deal with the most significant digits in the expansion. We start by rewriting the sum into an integral.

S(N, j, ν) = ∑_{p≤N} e (\frac{ν}{q^{j}} f(p)) = ∫_{2}^{N} e (\frac{ν}{q^{j}} f(t)) dπ(t) + O(1).

In the second step we then apply the prime number theorem. Thus

S(N, j, ν) = ∫_{N(log N)^{−G}}^{N} e (\frac{ν}{q^{j}} f(t)) \frac{dt}{log t} + O (\frac{N}{(log N)^{G}} ) .

Now we use the second mean-value theorem together with Lemma 10 and k = ⌊θ⌋ to get

S(N, j, ν) ≪ \frac{1}{log N} sup_{ξ} |∫_{N(log N)^{−G}}^{ξ} e (\frac{ν}{q^{j}} f(t)) dt| + O (\frac{N}{(log N)^{G}} )

≪ \frac{1}{log N} (\frac{|ν|}{q^{j}})^{− \frac{1}{k}} + O (\frac{N}{(log N)^{G}} ) .

(27)

4.3 Least significant digits

For the digits in this range we want to apply Vaughan’s identity in order to transfer the sum over the primes into two special types of sums involving products of integers. Before we may apply Vaughan’s identity we have to weight the exponential sum under consideration by the von Mangoldt function. By an application of Lemma 9, it suffices to consider an interval of the form (P, 2P]. Thus

|S(N, j, ν)| ≪ (log N) | ∑_{P <p≤2P} e (f(p))| .

Using partial summation we get

|S(N, j, ν)| ≪ (log N) | ∑_{P <p≤2P} e (f(p))| ≪ (log N)P^{\frac{1}{2}} + (log N) | ∑_{P <n≤P_{1}} Λ(n)e (f(n))|

for some P_{1} with P < P_{1} ≤ 2P. From now on we may assume that P > N^{1−η}. Then an application of Lemma 11 with U = P^{\frac{δ}{3}} , V = P^{\frac{1}{3}} , Z = P^{\frac{1}{2} − \frac{δ}{3}} yields

S(N, j, ν) ≪ P^{\frac{1}{2}} + (log P)^{7} |S_{1}| ,  (28)

where S_{1} is either a Type I sum as in (13) with Y ≥ P^{\frac{1}{2} − \frac{δ}{3}} or a Type II sum as in (14) with

P^{\frac{δ}{3}} ≤ Y ≤ P^{\frac{1}{3}} .

Suppose first that S_{1} is a Type II sum, i.e.,

S_{1} = ∑_{X<x≤X_{1}} a_{x} ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}} b_{y}e (f(xy)) .

Then an application of the Cauchy-Schwarz inequality yields

|S_{1}|^{2} ≤ ∑_{X<x≤X_{1}} |a_{x}|^{2} ∑_{X<x≤X_{1}} | ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}} b_{y}e (\frac{ν}{q^{j}} f(xy))|^{2}

≪ XP^{2ε} ∑_{Y <y≤Y_{1}} ∑_{Y <z≤Y_{1}} b_{y}\overline{b_{z}} ∑_{\begin{matrix}X<x≤X_{1} \\ P <xy,xz≤P_{1} \end{matrix}} e (\frac{ν}{q^{j}} (f(xy) − f(xz))) ,

where we have used that |a_{x}| ≪ P^{ε}. Collecting all the terms where y = z and using |b_{y}| ≪ P^{ε} yields

|S_{1}|^{2} ≪ XP^{4ε} (XY + ∑_{Y <y<z≤Y_{1}} | ∑_{\begin{matrix}X<x≤X_{1} \\ P <xy,xz≤P_{1} \end{matrix}} e (\frac{ν}{q^{j}} (f(xy) − f(xz)))|) .  (29)

There must be a pair (y, z) with Y < y < z < Y_{1} such that

|S_{1}|^{2} ≪ P^{2+4ε}Y^{−1} + P^{4ε}XY^{2} | ∑_{X_{2}<x≤X_{3}} e(g(x))| ,  (30)

where X_{2} = max(X, P y^{−1}), X_{3} = min(X_{1}, P_{1}z^{−1}) and

g(x) = \frac{ν}{q^{j}} (f(xy) − f(xz)) = \frac{ν}{q^{j}} α(y^{θ} − z^{θ})x^{θ}.

We will apply Lemma 12 to estimate the exponential sum. Setting

k := ⌈2θ⌉ + 1

we get that g^{(k+1)}(x) ∼ νq^{−j}αθ(θ − 1) ⋯ (θ − k)x^{θ−(k+1)}. Thus

λ ≤ \frac{g^{(k+1)}(x)}{(k + 1)!} ≤ c_{0}λ (X_{2} < x ≤ X_{3})

or similarly for −g^{(k+1)}(x), where

λ = cνq^{−j}α(y^{θ} − z^{θ})X^{θ−(k+1)}

and c depends only on θ and α.

Since θ > 1 we get

λ ≥ P^{δ−θ}Y^{θ−1}X^{θ−(k+1)} ≥ X^{−k− \frac{1}{2}} .

Similarly we obtain

λ ≤ P^{2δ}Y^{θ}X^{θ−(k+1)} ≪ P^{θ+2δ}X^{−(k+1)} ≤ X^{−1}.

Thus we get that X^{−k− \frac{1}{2}} ≤ λ ≤ X^{−1}. Therefore an application of Lemma 12 yields

∑_{X_{2}<x≤X_{3}} e(g(x)) ≪ X^{1−η},

where η depends only on k an therefore on θ. Inserting this in (30) we get

|S_{1}|^{2} ≪ P^{2+4ε}Y^{−1} + P^{4ε}XY^{2}X^{1−η} ≪ P^{2+4ε} (P^{−δ/3} + P^{−2η/3}) .  (31)

The case of S_{1} being a type I sum is similar but simpler. We have

|S| ≤ ∑_{X<x≤X_{1}} |a_{x}| | ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}}(log y)e (f(xy))| ≪ XP^{ε} | ∑_{\begin{matrix}Y <y≤Y_{1} \\ P <xy≤P_{1} \end{matrix}}(log y)e (f(xy))|

for some x with X < x ≤ X_{1}. By a partial summation we get

|S| ≪ XP^{ε} log P | ∑_{\begin{matrix}Y_{2}<y≤Y_{3} \\ P <xy≤P_{1} \end{matrix}} e (f(xy))|  (32)

for some Y ≤ Y_{2} < Y_{3} ≤ Y_{1}. Now we set

g(y) = f(xy) = \frac{ν}{q^{j}} αx^{θ}y^{θ}.

Again the idea is to apply Lemma 12 for the estimation of the exponential sum. We set

k := ⌈3θ⌉ + 2

and get for the k + 1-st derivative

λ ≤ \frac{g^{(k+1)}(x)}{(k + 1)!} ≤ c_{0}λ (X_{2} < x ≤ X_{3})

or similarly for −g^{(k+1)}(x), where

λ = c\frac{ν}{q^{j}} αx^{θ}Y^{θ−(k+1)}

and c again depends only on α and θ. We may assume that N and hence P is sufficiently large, then we get that

Y^{−(k+1)} ≪ P^{−θ}X^{θ}Y^{θ−(k+1)} ≤ λ ≤ P^{2δ}X^{θ}Y^{θ−(k+1)} ≪ P^{θ+2δ}Y^{−(k+1)} ≤ Y^{−1}.

Now an application of Lemma 2.5 yields

∑_{Y_{2}<y≤Y_{3}} e(g(y)) ≪ Y^{1−η},

where η depends only on k and thus on θ. Inserting this in (32) we get

|S_{1}| ≪ (log P)XP^{ε}Y^{1−η} ≪ (log P)P^{1+ε−η(1/2−δ/3)}.  (33)

Combining (33) and (31) in (28) yields

|S(N, j, ν)| ≪ P^{\frac{1}{2}} + (log P)^{7} (P^{1+2ε} (P^{−δ/6} + P^{−η/3}) + (log P)P^{1+ε−η(1/2−δ/3)})
≪ P^{\frac{1}{2}} + (log P)^{8} P^{1−σ}.

(34)

4.4 Conclusion

On the one hand summing (27) over j and ν yields

∑_{1≤|ν|≤H} |ν|^{−1} ∑_{N^{θ−δ}<q^{j}≤N^{θ}} S(N, j, ν)

≪ ∑_{1≤|ν|≤H} |ν|^{−1} ∑_{N^{θ−δ}<q^{j}≤N^{θ}} (\frac{1}{log N} (\frac{|ν|}{q^{j}})^{− \frac{1}{k}} + O (\frac{N}{(log N)^{G}} ))

≪ \frac{1}{log N} ∑_{1≤|ν|≤H} |ν|^{−1− \frac{1}{k}} ∑_{N^{θ−δ}<q^{j}≤N^{θ}} q^{− \frac{j}{k}} + O (\frac{N}{(log N)^{G−2}} )

≪ \frac{N}{log N} .

On the other hand in (34) we sum over j and ν and get

∑_{1≤|ν|≤H} |ν|^{−1} ∑_{q^{ℓ}≤q^{j}≤N^{θ−δ}} S(N, j, ν) ≪ (log N)^{2}N^{\frac{1}{2}} + (log N)^{10}N^{1−σ′}.

Combining these estimates in (26) finally yields

|∑_{p≤N} N^{∗}(f(p)) − \frac{π(N)}{q^{ℓ}}J| ≪ \frac{N}{log N}

and the proposition is proved.

5 Acknowledgment

The authors thank the anonymous referee, who read the manuscript very carefully and his/her suggestions considerably improved the presentation of the results.

References

[1] J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.

[2] R. C. Baker and G. Kolesnik. On the distribution of p^{α} modulo one. J. Reine Angew. Math. 356 (1985), 174–193.

[3] A. Balog. On the fractional part of p^{θ}. Arch. Math. (Basel) 40 (1983), 434–440.

[4] A. Balog. On the distribution of p^{θ} mod 1. Acta Math. Hungar. 45 (1985), 179–199.

[5] V. Bergelson, G. Kolesnik, M. Madritsch, Y. Son, and R. Tichy. Uniform distribution of prime powers and applications to van der Corput sets. Submitted, 2012.

[6] E. Borel. Les probabilités dénombrables et leurs applications arithmétiques. Palermo Rend. 27 (1909), 247–271.

[7] X. Cao and W. Zhai. On the distribution of p^{α} modulo one. J. Théor. Nombres Bordeaux 11 (1999), 407–423.

[8] D. G. Champernowne. The construction of decimals normal in the scale of ten. J. Lond. Math. Soc. 8 (1933), 254–260.

[9] A. H. Copeland and P. Erdös. Note on normal numbers. Bull. Amer. Math. Soc. 52 (1946), 857–860.

[10] H. Davenport and P. Erdös. Note on normal decimals. Canadian J. Math. 4 (1952), 58–63.

[11] M. Drmota and R. F. Tichy. Sequences, Discrepancies and Applications, Vol. 1651 of Lecture Notes in Mathematics. Springer-Verlag, 1997.

[12] J.-M. Dumont and A. Thomas. Modifications de nombres normaux par des transducteurs. Acta Arith. 68 (1994), 153–170.

[13] S. W. Graham and G. Kolesnik. Van der Corput’s Method of Exponential Sums, Vol. 126 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1991.

[14] G. Harman. On the distribution of \sqrt{p} modulo one. Mathematika 30 (1983), 104–116.

[15] E. Heppner. Über die Summe der Ziffern natürlicher Zahlen. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 19 (1976), 41–43.

[16] I. Kátai. On the sum of digits of primes. Acta Math. Acad. Sci. Hungar. 30 (1977), 169–173.

[17] R. M. Kaufman. The distribution of {√p}. Mat. Zametki 26 (1979), 497–504, 653.

[18] Manfred G. Madritsch. The summatory function of q-additive functions on pseudopolynomial sequences. J. Théor. Nombres Bordeaux 24 (2012), 153–171.

[19] M. G. Madritsch, J. M. Thuswaldner, and R. F. Tichy. Normality of numbers generated by the values of entire functions. J. Number Theory 128 (2008), 1127–1145.

[20] Y. Nakai and I. Shiokawa. A class of normal numbers. Japan. J. Math. 16 (1990), 17–29.

[21] Y. Nakai and I. Shiokawa. Discrepancy estimates for a class of normal numbers. Acta Arith. 62 (1992), 271–284.

[22] Y. Nakai and I. Shiokawa. Normality of numbers generated by the values of polynomials at primes. Acta Arith. 81 (1997), 345–356.

[23] J. Schiffer. Discrepancy of normal numbers. Acta Arith. 47 (1986), 175–186.

[24] J. Schoissengeier. Eine neue Diskrepanz für gewisse Primzahlfolgen. Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II 187 (4-7) (1978), 219–224.

[25] J. Schoissengeier. The connection between the zeros of the ζ-function and sequences (g(p)), p prime, mod 1. Monatsh. Math. 87 (1979), 21–52.

[26] I. Shiokawa. On the sum of digits of prime numbers. Proc. Japan Acad. 50 (1974), 551–554.

[27] S. Srinivasan and R. F. Tichy. Uniform distribution of prime power sequences. Anz. Österreich. Akad. Wiss. Math.-Natur. Kl. 130 (1993), 33–36.

[28] E. C. Titchmarsh. The Theory of The Riemann Zeta-Function, second edition. Oxford University Press, 1986.

[29] D. I. Tolev. On the simultaneous distribution of the fractional parts of different powers of prime numbers. J. Number Theory 37 (1991), 298–306.

[30] I. M. Vinogradov. The Method of Trigonometrical Sums in The Theory of Numbers. Translated from the Russian, revised and annotated by K. F. Roth and Anne Davenport, reprint of the 1954 translation. Dover Publications Inc., 2004.

[31] W. Zhai. On the simultaneous distribution of the fractional parts of different powers of prime numbers. J. Number Theory 86 (2001), 133–155.

2010 Mathematics Subject Classification: Primary 11N37; Secondary 11A63. Keywords: normal number, pseudo-polynomial.

Received July 23 2012; revised version received October 31 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.