On the exponential sum with the sum of digits of hereditary base b notation

(1)

27 July 2021

Original Citation:

On the exponential sum with the sum of digits of hereditary base b notation

Terms of use:

Open Access

(Article begins on next page)

Anyone can freely access the full text of works made available as "Open Access". Works made available under a

Creative Commons license can be used according to the terms and conditions of said license. Use of all other works

requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law.

Availability:

This is the author's manuscript

(2)

ON THE EXPONENTIAL SUM WITH THE SUM OF DIGITS OF

HEREDITARY BASE b NOTATION

Carlo Sanna

Department of Mathematics, Universit`

a degli Studi di Torino, Turin, Italy

carlo.sanna.dev@gmail.com

Received: , Revised: , Accepted: , Published:

Abstract

Let b ≥ 2 be an integer and w

b

(n) be the sum of digits of the nonnegative integer

n written in hereditary base b notation. We give optimal upper bounds for the

exponential sum

P

N −1

n=0

exp(2πiw

b

(n)t), where t is a real number. In particular, our

results imply that for each positive integer m the sequence {w

b

(n)}

∞n=0

is uniformly

distributed modulo m; and that for each irrational real α the sequence {w

b

(n)α}

∞n=1

is uniformly distributed modulo 1.

1. Introduction

Let b ≥ 2 be an integer. Exponential sums involving s

b

(·), the base b sum of digits

function, has been studied extensively [3] [12] [6] [1], primarily in relation to

prob-lems of uniform distribution. Similar exponential sums have been also investigated

with respect to alternative digital expansions. For example, digital expansions

aris-ing from linear recurrences [5] [9], complex base number systems [10] [2] and number

systems for number fields [14] [11]. We study the exponential sum

S

b

(t, N ) :=

N −1

X

n=0

e(w

b

(n) t),

where N is a positive integer, t ∈ R \ Z and w

b

(n) is the sum of digits of n written

in hereditary base b notation.

The hereditary base b notation of a nonnegative integer n is obtained as follows:

write n in base b, then write all the exponents in base b, etc. until there appear only

the numbers 0, 1, . . . , b. For example, the hereditary base 3 notation of 4384 is

1 · 3

0

+ 1 · 3

2·30

+ 2 · 3

1·30+2·31·30

.

(3)

the related Goodstein theorem [4], which can be considered the first simple example

of a statement, true in ZFC set theory, that is unprovable in Peano arithmetic [7].

So we define w

b

(n) as the sum of digits of n written in hereditary base b notation,

to continue the example:

w

3

(4384) = 1 + 1 + 2 + 2 + 1 + 2 + 1 = 10.

More precisely, the function w

b

(·) can be defined recursively as follows:

w

b

(0) := 0,

w

b

(n) :=

u

X

j=1

(w

b

(k

j

) + a

j

)

for n =

u

X

j=1

a

j

b

kj

,

where u ≥ 1, 0 ≤ k

1

< . . . < k

u

are integers and a

1

, . . . , a

u

∈ {1, 2, . . . , b − 1}.

We give upper bounds for S

b

(t, N ), distinguishing between rational and irrational t.

Theorem 1.1. Let t = `/m, with 1 ≤ |`| < m relatively prime integers.

(i). If m | b then S

b

(t, N ) = e(w

b

(N )) P

b

(t, N ) for N ≥ 1, where P

b

(t, ·) is a

periodic function of period b.

(ii). If m is even and m | (b − 2), then S

b

(t, N ) = e(w

b

(N )) Q

b

(t, N ) for N ≥ 1,

where Q

b

(t, ·) is a periodic function of period b

k

0₊₁

and k

0

is the least

non-negative integer such that 2(w

b

(k

0

) + 1)/m is an odd integer.

(iii). If m | (b − 1) then S

b

(t, N ) = O

b

(log N ) for N > 1.

(iv). If we are not in cases (i), (ii) or (iii), then for ε > 0 it results

S

b

(t, N ) = O

b,t,ε

(N

Cb,t+ε

)

for N ≥ 1, where the constant

C

b,t

:=

1 m

log

b

1 − (−1)

m+b`

sin(π(b − 1)t)

sin(πt)

m

∈ ]0, 1[

is the best possible.

Theorem 1.2. If b ≥ 3 and t is irrational, then for ε > 0 it results

S

b

(t, N ) = O

b,t,ε

(N

Cb,t+ε

)

for N ≥ 1, where the constant

C

b,t

:= max

0, log

_b

sin(π(b − 1)t)

sin(πt)

∈ [0, 1[

is the best possible.

(4)

INTEGERS: 14 (2014)

3 Unfortunately, in the case in which b = 2 and t is irrational, we have not been

able to prove an upper bound for S

b

(t, N ) similar to that of Theorem 1.2. We

explain later why our arguments are not enough for that. However, for b ≥ 2 and

t ∈ R \ Z we have at least the crude upper bound S

b

(t, N ) = o(N ) as N → ∞

(see Lemma 2.4). Therefore, we obtain the following corollaries (see [8, Chap. 1,

Theorem 2.1] and [8, Chap. 5, Corollary 1.1]).

Corollary 1.1. For each positive integer m, the sequence {w

b

(n)}

∞n=0

is uniformly

distributed modulo m, i.e.,

lim

x→∞

#{n ≤ x : w

b

(n) ≡ r mod m}

x

=

1 m

for all r = 1, 2, . . . , m.

Corollary 1.2. For each irrational real α, the sequence {w

b

(n)α}

∞n=0

is uniformly

distributed modulo 1, i.e.,

lim

x→∞

#{n ≤ x : (w

b

(n)α mod 1) ∈ [a, b]}

x

= b − a

for all 0 ≤ a ≤ b ≤ 1.

Notations

Through the paper, we reserve the variables `, m, n, M , N , u, h, r, k and k

j

for

integers. We use the Bachmann–Landau symbols O and o, as well as the Vinogradov

symbols and , with their usual meanings. We write

D

b

:= {1, 2, . . . , b − 1} for

the set of nonzero base b digits and e(x) := e

2πix

_{for the standard additive character.}

We adopt the usual convention that empty sums and empty products, e.g.

P

y

n=x

and

Q

y

n=x

with x > y, have values 0 and 1, respectively.

2. Preliminaries to proofs of Theorem 1.1 and 1.2

Proposition 2.1. If k ≥ 0, a ∈

D

b

and 0 ≤ n < b

k

, then

w

b

(ab

k

+ n) = w

b

(k) + w

b

(n) + a.

Proof. It is a straightforward consequence of the definition of w

b

(·).

Proposition 2.2. If k ≥ 0, a ∈

D

b

and 0 < N ≤ b

k

, then

(5)

Proof. Consider that

S

b

(t, ab

k

+ N ) = S

b

(t, ab

k

) +

N −1

X

n=0

e(w

b

(ab

k

+ n) t)

= S

b

(t, ab

k

) + e((w

b

(k) + a) t)

N −1

X

n=0

e(w

b

(n) t)

= S

b

(t, ab

k

) + e((w

b

(k) + a) t) S

b

(t, N ),

where we have applied Proposition 2.1.

For the next lemma, we define

E

b

(t, a, θ) := 1 + e(θ +

1₂

a t) ·

sin(π(a − 1)t)

sin(πt)

,

F

b

(t, a, r) := E

b

(t, a, rt),

f

b

(t, a, h) := F

b

(t, a, w

b

(h)),

for a ∈

D

b

, θ ∈ R and r, h ≥ 0.

Lemma 2.3. If k ≥ 0 and a ∈

D

b

then

S

b

(t, ab

k

) = f

b

(t, a, k)

k−1

Y

h=0

f

b

(t, b, h).

Moreover, if N =

P

u j=1

a

j

b

kj

, where u ≥ 1, a

1

, . . . , a

u

∈

D

b

and 0 ≤ k

1

< · · · < k

u

,

then

S

b

(t, N ) = e(w

b

(N ) t)

u

X

j=1

e

−

j

X

v=1

(w

b

(k

v

) + a

v

) t

!

S

b

(t, a

j

b

kj

).

Proof. By Proposition 2.2 (with N = b

k

_{), we see that}

S

b

(t, (a + 1)b

k

) = S

b

(t, ab

k

) + e((w

b

(k) + a) t) S

b

(t, b

k

).

As a consequence, by induction, we obtain

S

b

(t, (a + 1)b

k

) =



1 +

a

X

j=1

e((w

b

(k) + j) t)



S

b

(t, b

k

)

=

1 + e((w

b

(k) + 1) t) ·

e(a t) − 1

e(t) − 1

S

b

(t, b

k

)

= f

b

(t, a + 1, k) S

b

(t, b

k

).

(6)

INTEGERS: 14 (2014)

5 But f

b

(t, 1, k) = 1, so that S

b

(t, cb

k

) = f

b

(t, c, k) S

b

(t, b

k

) for each c ∈

D

b

∪ {b}. In

particular, S

b

(t, b

k+1

) = f

b

(t, b, k) S

b

(t, b

k

) for c = b. Thus, since S

b

(t, 1) = 1, we

find that

S

b

(t, ab

k

) = f

b

(t, a, k) S

b

(t, b

k

) = f

b

(t, a, k)

k−1

Y

h=0

f

b

(t, b, h),

and the first part of the claim is proved.

Now, from Proposition 2.2, we get that

S

b

(t, N + 1) = S

b

(t, a

u

b

ku

) + e((w

b

(k

u

) + a

u

) t) S

b

(t, N + 1 − a

u

b

ku

)

(1)

= S

b

(t, a

u

b

ku

) + e((w

b

(k

u

) + a

u

) t) S

b

(t, a

u−1

b

ku−1

) + · · ·

=

u

X

j=1





u

Y

v=j+1

e((w

b

(k

v

) + a

v

) t)



S

b

(t, a

j

b

kj

) + e(w

b

(N ) t).

Subtracting e(w

b

(N ) t) from (1) and recalling that w

b

(N ) =

P

u

j=1

(w

b

(k

j

) + a

j

),

the second part of the claim follows.

Lemma 2.4. S

b

(t, N ) = o(N ) as N → ∞.

Proof. Let a ∈

D

b

and k ≥ 0. From Lemma 2.3, we know that

|S

b

(t, ab

k

)|

ab

k

=

|f

b

(t, a, k)|

a

k−1

Y

h=0

|f

b

(t, b, h)|

b

.

(2)

We claim that the right-hand side of (2) tends to 0 as k → ∞. Observe that

|f

b

(t, a, k)| ≤ a and

|f

b

(t, b, h)|

b

≤

1 b

1 +

sin(π(b − 1)t)

sin(πt)

≤ 1

(3)

for all h ≥ 0, so that the product in (2) is a nonincreasing function of k. If b ≥ 3

then the last inequality in (3) is strict, so the claim follows. If b = 2 then, for all

h ≥ 0,

|f

b

(t, b, h)|

b

= | cos(π(w

b

(h) + 1)t)|.

On the one hand, if t is rational, then the sequence {| cos(πrt)|}

∞_r=1

is periodic and,

since t is not an integer, it has infinitely many terms less than 1. On the other hand,

if t is irrational, then the sequence {| cos(πrt)|}

∞_r=1

is dense in [0, 1]. In any case,

there exists δ < 1 and an infinitude of positive integers r such that | cos(πrt)| ≤ δ.

Since w

b

(·) is surjective, we get that |f

b

(t, b, h)|/b < δ for infinitely many h ≥ 0,

and the claim follows again.

At this point, we know that |S

b

(t, ab

k

)|/(ab

k

) → 0 as k → ∞. Let

L := lim sup

N →∞

|S

b

(t, N )|

(7)

so that L ∈ [0, 1]. Put a = a(N ), k = k(N ) and M = M (N ) as functions of N ≥ 1

such that N = ab

k

_{+ M and 0 ≤ M < b}

k

_{. Then by Proposition 2.2 and the above,}

we have

L = lim sup

N →∞

|S

b

(t, ab

k

+ M )|

ab

k

_{+ M}

≤ lim sup

N →∞

|S

b

(t, ab

k

)|

ab

k

_{+ M}

+ lim sup

N →∞

|S

b

(t, M )|

ab

k

_{+ M}

≤ lim sup

k→∞

|S

b

(t, ab

k

)|

ab

k

+

1

2 lim sup

M →∞

|S

b

(t, M )|

M

= 0 +

1₂

L,

so that L = 0, as desired.

Proposition 2.5. We have F

b

(t, b, r) = 0 for some r ∈ Z if and only if t = `/m,

where ` and m 6= 0 are relatively prime integers such that:

(a) m | b and m | r; or

(b) m is even, m | (b − 2),

1₂

m | (r + 1) and 2(r + 1)/m is odd.

Proof. If cases (a) or (b) hold, then we quickly deduce that F

b

(t, b, r) = 0. On the

other hand, if F

b

(t, b, r) = 0 then necessarily | sin(π(b − 1)t)| = | sin(πt)|, so that

at least one of bt and (b − 2)t is an integer. If bt is an integer then F

b

(t, b, r) =

1 − e(rt) = 0, so also rt is an integer. Hence, t = `/m for some relatively prime

integers ` and m 6= 0 such that m | b and m | r, this is case (a). If (b − 2)t is an

integer then F

b

(t, b, r) = 1 + e((r + 1)t) = 0, so that (r + 1)t = u +

1₂

for some

integer u. Hence, t = (2u + 1)/(2r + 2) = `/m for some relatively prime integers

` and m 6= 0 such that m is even, m | (b − 2) and 2(r + 1)/m is odd, this is case

(b).

Proposition 2.6. If t is irrational and b ≥ 3 then E

b

(t, b, θ) 6= 0 for all θ ∈ R.

Proof. As in the proof of Proposition 2.5, if E

b

(t, b, θ) = 0 then | sin(π(b − 1)t)| =

| sin(πt)|, so that at least one of bt and (b − 2)t is an integer, but this is impossible,

since t is irrational and b ≥ 3.

3. Proof of Theorem 1.1

First, suppose that k

00

is a nonnegative integer such that f

b

(t, b, k

00

) = 0. Then,

by Lemma 2.3, we have that S

b

(t, ab

k

) = 0 for all a ∈

D

b

and k > k

00

. Moreover,

again by Lemma 2.3, it results that S

b

(t, N ) = e(w

b

(N ) t) R

b

(t, N ) for any N ≥ 1,

where R

b

(t, ·) is a function depending only on (N mod b

k

00₊₁

(8)

INTEGERS: 14 (2014)

7 necessarily minimal) period b

k00+1

. Therefore, by Proposition 2.5, the claim follows

in case (i), taking k

00

= 0, and in case (ii), taking k

00

= k

0

.

Now suppose we are in case (iii), i.e., m | (b − 1). Then f

b

(t, b, h) = 1 for all

h ≥ 0, so that from Lemma 2.3 we get S

b

(t, b

k

) = 1 for all k ≥ 0. Taking N as in

Lemma 2.3, we find that

|S

b

(t, N )| ≤

u

X

j=1

|S

b

(t, a

j

b

kj

)| ≤ (b−1)

u

X

j=1

|S

b

(t, b

kj

)| = (b−1)u ≤ (b−1)(log

b

N +1).

Hence, S

b

(t, N ) = O

b

(log N ) for any N > 1, as claimed.

Finally, suppose we are in case (iv). So by Proposition 2.5, f

b

(t, b, h) 6= 0 for all

h ≥ 0. Thus, Lemma 2.3 yields

lim

k→∞

log

_b

|S

b

(t, b

k

)|

k

= lim

k→∞

1 k

k−1

X

h=0

log

_b

|f

b

(t, b, h)|

= lim

k→∞

1 k

k−1

X

h=0

log

_b

|F

b

(t, b, w

b

(h))| =

1 m

m

X

r=1

log

_b

|F

b

(t, b, r)|,

where the last equality follows since, by Corollary 1.1, {w

b

(n)}

∞n=1

is uniformly

distributed modulo m and log |F

b

(t, b, ·)| is a function of period m. Observe that

m

Y

r=1

|1 + e(rt)z| = |1 − (−z)

m

|

for any complex number z, thus putting z = e(

1

2

bt) sin(π(b − 1)t)/ sin(πt) we have

1 m

m

X

r=1

log

b

|F

b

(t, b, r)| =

1 m

log

b

1 − (−1)

m+b`

sin(π(b − 1)t)

sin(πt)

m

= C

b,t

.

From here, we get

|S

b

(t, b

k

)| = (b

k

)

Cb,t+o(1)

,

(4)

as k → ∞. Therefore, if ε > 0 then S

b

(t, b

k

)

b,t,ε

(b

k

)

Cb,t+ε

for any k ≥ 0, and

taking N as in Lemma 2.3 yields that

|S

b

(t, N )| ≤

u

X

j=1

|S

b

(t, a

j

b

kj

)| ≤ (b − 1)

u

X

j=1

|S

b

(t, b

kj

)|

b,t,ε u

X

j=1

(b

kj

₎

Cb,t+ε

b,t,ε ku

X

k=0

(b

k

)

Cb,t+ε

b,t,ε

(b

ku

)

Cb,t+ε

≤ N

Cb,t+ε

(9)

Now we prove that C

b,t

∈ ]0, 1[. On the one hand, it must be C

b,t

≥ 0, otherwise

S

b

(t, N ) → 0 as N → ∞, which is absurd. If C

b,t

= 0 then, since sin(π(b − 1)t) 6= 0,

it results

2 = (−1)

m+b`

sin(π(b − 1)t)

sin(πt)

m

=

−

e((b − 1)t) − 1

e(t) − 1

m

,

so that Q

m

√

_{2 is a subfield of Q(e(t)), but}

Q

m

√

2 : Q = m > φ(m) = [Q(e(t)) : Q],

where φ(·) is the totient function, which is a contradiction, hence C

b,t

> 0. On the

other hand, since m ≥ 2, we see that

C

b,t

≤

1 m

log

b

1 +

sin(π(b − 1)t)

sin(πt)

m

≤

1 m

log

b

(1 + (b − 1)

m

_{) < 1.}

It remains only to prove that C

b,t

is the best constant possible for the bound

obtained, i.e., that for any C < C

b,t

there exists ε > 0 such that S

b

(t, N ) 6=

O

b,t,ε

(N

C+ε

), as N → +∞. This is straightforward since if ε ∈ ]0, C

b,t

− C[ then

from (4) we get

|S

b

(t, b

k

)| = (b

k

)

Cb,t−C−ε+o(1)

· (b

k

)

C+ε

6= O

b,t,ε

((b

k

)

C+ε

),

as k → ∞, so a fortiori S

b

(t, N ) 6= O

b,t,ε

(N

C+ε

). This completes the proof.

4. Proof of Theorem 1.2

Observe that, since b ≥ 3 and t is irrational, by Proposition 2.6 it follows that

log

b

|E

b

(t, b, ·)| is a well defined function. On the other hand, since t is irrational,

Proposition 2.5 shows that f

b

(t, b, h) 6= 0 for all h ≥ 0. Thus, by Lemma 2.3,

lim

k→∞

log

_b

|S

b

(t, b

k

)|

k

= lim

k→∞

1 k

k−1

X

h=0

log

_b

|f

b

(t, b, h)|

(5)

= lim

k→∞

1 k

k−1

X

h=0

log

_b

|E

b

(t, b, w

b

(h)t)| =

Z

1 0

log

_b

|E

b

(t, b, θ)| dθ,

since log

_b

|E

b

(t, b, ·)| is a continuous function of period 1 and, by Corollary 1.2, the

sequence {w

b

(h)t}

∞h=0

is uniformly distributed modulo 1 (see [8, Chap. 1, Corollary

1.2]). Now, from Jensen’s formula [13, Theorem 15.18], we know that

Z

1

0

log |1 + e(θ)A| dθ =

(

log |A|

if |A| > 1

0 if |A| ≤ 1

(10)

INTEGERS: 14 (2014)

9 for all complex number A. Putting A = e(

1₂

b t) sin(π(b − 1)t)/ sin(πt) we can

eval-uate the integral in (5) and get

Z

1 0

log

_b

|E

b

(t, b, θ)| dθ = max

0, log

_b

sin(π(b − 1)t)

sin(πt)

= C

b,t

.

Hence, S

b

(t, b

k

) = (b

k

)

Cb,t+o(1)

as k → ∞. At this point, the claim follows by the

same arguments used at the end of the proof of Theorem 1.1.

5. Concluding remarks

It is perhaps interesting that, in the proof of Theorem 1.1 (respectively Theorem

1.2), we used a coarse upper bound on S

b

(t, N ), namely Lemma 2.4, to get that

{w

b

(n)}

∞n=1

is uniformly distributed modulo m (respectively {w

b

(n)α}

∞n=1

is

uni-formly distributed modulo 1), and then we used this result to get an improved upper

bound on S

b

(t, N ).

An open question is if it is possible to get an upper bound, similar to that of

Theorem 1.2, for S

2

(t, N ) when t is irrational. Note that we cannot use the same

arguments as in the proof of Theorem 1.2, because Proposition 2.6 breaks down for

b = 2. Precisely, the function log

₂

|E

2

(t, 2, ·)| = log

2

|1 + e( · + t)| has singularities

on Z + (

1

2

− t) and although the integral

Z

1

0

log

2

|E

2

(t, 2, θ)| dθ

exists finite (in fact, it is equal to zero), it is no longer true that

Z

1 0

log

₂

|E

2

(t, 2, θ)| dθ = lim

k→∞

1 k

k−1

X

h=0

log

₂

|E

2

(t, 2, θ

h

)|

for any sequence {θ

h

}

∞h=0

which is uniformly distributed modulo 1. For example, for

all h ≥ 0 not a power of 2 take θ

h

:= θ

0h

, where {θ

0h

}

∞h=0

is some sequence uniformly

distributed modulo 1; and for all n ≥ 0 take θ

2n

such that

P

2 n

h=0

log

2

|E

2

(t, 2, θ

h

)| <

−(2

n

_{+ 1). We left to the reader to prove that then {θ}

h

}

∞h=0

is uniformly distributed

modulo 1 and

lim inf

k→∞

1 k

k−1

X

h=0

log

₂

|E

2

(t, 2, θ

h

)| ≤ −1.

Acknowledgements

The author are very grateful to Salvatore Tringali (Laboratoire Jacques-Louis Lions)

for many useful comments.

(11)