A Simpler Normal Number Construction for Simple Lüroth Series

J. Vandehey University of Georgia at Athens Department of Mathematics Athens, GA 30602 USA

                   vandehey@uga.edu

Abstract

Champernowne famously proved that the number

0.(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12) ⋯

formed by concatenating all the integers one after another is normal to base 10. We give a generalization of Champernowne’s construction to various other digit systems, including generalized Lüroth series with a finite number of digits. For these systems, our construction simplifies a recent construction given by Madritsch and Mance. Along the way we give an estimation of the sum of multinomial coefficients above a tilted hyperplane in Pascal’s simplex, which may be of general interest.

1 Introduction

A number x ∈ [0, 1) with base b expansion x = 0.d_{1}d_{2}d_{3} ⋯ is said to be normal to base b if for any string s = a_{1}a_{2} ⋯ a_{k} of base b digits, we have

lim_{N→∞} \frac{#\{0 ≤ n ≤ N | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} = b^{−k}.

This may be interpreted as saying that for a normal number x, each digit string appears with the same relative frequency as every other digit string having the same length.

While many methods (most notably the Birkhoff ergodic theorem) can be used to show that almost all real numbers x ∈ [0, 1) are normal to any fixed base b, we know of very few examples of normal numbers. None of the well-known irrational constants, such as e or π, are known to be normal to any base, and the only examples we have of normal numbers are those explicitly constructed to be normal. The first and still most famous of these constructions is Champernowne’s constant [7], which in base 10 looks like

0.(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13) ⋯,

formed by concatenating all the integers in succession. He derived this construction after proving the base 10 normality of the following number

0.(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(00)(01)(02)(03) ⋯,  (1)

formed by concatenating all base 10 digit strings of length 1 in lexicographical order, then all the digit strings of length 2 in lexicographical order, and so on.

Constructions for base b normal numbers usually fall into one of three methods: the combinatorial method first introduced by Copeland and Erdős [8], that is perhaps the most natural generalization of Champernowne’s techniques; the exponential sum method first introduced by Davenport and Erdős [10]; and the method of pseudo-random number generators used most powerfully by Bailey and Crandall [2, 3].

Recently, mathematical interest has turned to providing constructions of normal numbers in other systems. In many cases, these proofs draw from techniques used by Champernowne, Copeland, and Erdős. We shall be concerned here with ergodic fibred systems [5, 17]. Common examples of fibred systems include base b expansions, continued fraction expansions, generalized Lüroth series, and β-expansions.

Definition 1. Ergodic fibred systems consist with a transformation T that maps a set Ω to itself, a measure μ on Ω that is finite and T -invariant, a digit set D ⊂ ℕ, and a countable collection of disjoint subsets {I_{d}}_{d∈D} such that every point in Ω is in some I_{d}. The map T is injective on each subset I_{d} and T is ergodic with respect to μ, i.e., for every A ⊂ Ω with T^{−1}A = A (up to some set of μ-measure 0), either μ(A) = 0 or μ(A) = 1.

The T -expansion of a point x ∈ Ω is then given by x = [d_{1}, d_{2}, d_{3}, …] where d_{n} is defined by T^{n−1}x ∈ I_{d_{n}}.^{1} For a given fibred system, we say a point x ∈ Ω with expansion x = [d_{1}, d_{2}, d_{3}, …] is T -normal if for any string s = [a_{1}, a_{2}, …, a_{k}] of digits from D we have

lim_{N→∞} \frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} = μ(C[s]).  (2)

where C[s] is the cylinder set for the string s, i.e.,

C[s] = {x = [d_{1}, d_{2}, …] | d_{i} = a_{i}, 1 ≤ i ≤ k}.

We will often denote the measure of a cylinder set s by λ_{s}, and if s consists of a single digit d, then we will often shorthand the measure of the set C[d] by λ_{d}.

1Our definitions here, in particular the part where {I_{d}}_{d∈D} form a partition of Ω, are somewhat nonstandard, but they guarantee that these expansions always exist and are unique for a given x.

We will denote the number of digits in the digit set D by D, and often assume that D = {1, 2, …, D}.

Madritsch and Mance [12] recently provided a normal number construction that works for many ergodic fibred systems, including those listed above. Their construction works roughly as follows:

1. Let ϵ_{k} be some small positive number shrinking to 0 very quickly as k increases, and let S_{k} = {s_{1}, s_{2}, s_{3}, …, s_{n}} be a set enumerating all strings of length k whose corresponding cylinder sets have measure at least ϵ_{k}.

2. Let M_{k} be at least 1/ϵ_{k}, and construct a string X_{k} formed by concatenating first ⌊M_{k}λ_{s_{1}}⌋ copies of s_{1}, then ⌊M_{k}λ_{s_{2}}⌋ copies of s_{2} and so on until ending with ⌊M_{k}λ_{s_{n}}⌋ copies of s_{n}. By construction, we expect that for strings s with length much smaller than k that s should appear in X_{k} with close to the correct frequency.

3. We chose a quickly growing sequence l_{k} and construct a digit x by first concatenating l_{1} copes of X_{1}, then l_{2} copies of X_{2}, and so forth. The l_{k}’s are chosen so that l_{k} copies of X_{k} are vastly longer than the concatenated copies of X_{1} up to X_{k−1} that precede it.

The strings X_{k} are constructed to have better and better small-scale normality properties and then are repeated so many times in the construction of x that their behavior swamps the behavior of what came before them. This construction was based on earlier work of Altomare and Mance [1], and Mance [13, 14] independently. The construction also bears resemblence to an earlier, but less general construction of Martinelli [15], although their results appear to be independent.

The advantage of the Madritsch-Mance construction is that it is extremely general, working even for the notoriously difficult β-expansions. The disadvantage of the Madritsch-Mance construction is its inefficency. For example, if we apply the Madritsch-Mance construction to create a normal number to base 10, it, like Champernowne’s secondary construction (1), concatenates every digit string at some point; however, while Champernowne’s second construction uses each digit string exactly 1 time, the Madritsch-Mance construction concatenates a string of length k at least k^{2k} log k times.

A different construction, by Bertrand-Mathis and Volkmann [6], is more efficient than the Madritsch-Mance construction; however it is more restricted in application. Bertrand-Mathis and Volkmann treat their dynamical systems symbolically, and their results only apply to symbolic dynamical systems with maximal entropy (so they would apply to base 10 expansions, but not to any other dynamical systems which are symbolically equivalent to base 10 expansions, such as generalized Lüroth series with 10 digits, see citation below).

Our goal in this paper is to construct and prove a normal number construction that is simpler than the Madritsch-Mance construction in that, like Champernowne’s construction, uses each digit string one time, and that also works for certain systems where the Bertrand-Mathis and Volkmann construction does not.

Definition 2. Given an ergodic fibred system, let S = {s_{n}}_{n∈ℕ} be an enumeration of all possible finite length strings ordered according to the following rule: If λ_{s_{i}} > λ_{s_{j}}, then i < j. (We do not care how strings whose cylinder sets have the same measure are ordered compared to one another. Although, if we want a rigorous definition of S, we may impose a lexicographical order on these strings.)

Let x_{S} be the point constructed by concatenating the strings s_{i} in order.

Note that if we consider a base 10 fibred system and impose a lexicographical ordering on those strings in S whose cylinder sets have the same measure, then we in fact get Champernowne’s second construction (1) precisely. Therefore the construction of x_{S} given in Definition 2 is a true generalization of Champernowne’s construction to other ergodic fibred systems.

Our goal in this paper will be to prove the following statement.

Theorem 3. Consider an ergodic fibred system generated by a transformation T such that D is finite and such that for each string s = [a_{1}, a_{2}, …, a_{k}], we have λ_{s} ≍ λ_{a_{1}}λ_{a_{2}} ⋯ λ_{a_{k}}.

For such a system, the number x_{S} constructed in Definition 2 is T -normal.

The simplest example of such a fibred system are the generalized Lüroth series with finitely many digits, where we have, in fact, λ_{s} = λ_{a_{1}}λ_{a_{2}} ⋯ λ_{a_{k}}. A good introduction to generalized Lüroth series is given in [9, Section 2.3].

We note that for some fibred systems, there may not be a point x ∈ Ω with T -expansion given by x_{S}. This is due to the possibility of inadmissable strings, strings s such that λ_{s} = 0. β-expansions, in particular, have many inadmissable strings, and in the Madritsch-Mance construction, they get around this obstruction by including padding, a long, but finite string of 0’s inserted before each concatenated string s_{i}.

However, the condition in Theorem 3 that λ_{s} ≍ λ_{a_{1}}λ_{a_{2}} ⋯ λ_{a_{k}} guarantees that no inadmissable strings exist.

We leave as an open question—since we do not yet have enough information to be willing to state it as a conjecture—whether this construction works for other fibred systems, including generalized Lüroth series with an infinite number of digits, continued fraction expansions, and (with an appropriate padding, à la Madritsch-Mance) β-expansions.

In the proof we shall make use of the following theorem, known alternately as Pjatetskii-Shapiro normality criterion or the hot spot theorem [4, 16].

Theorem 4 (Pjatetskii-Shapiro). A point x with expansion x = [d_{1}, d_{2}, d_{3}, …] is T -normal if for any string s = [a_{1}, a_{2}, …, a_{k}] we have

lim sup_{N→∞} \frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} ≤ c · λ_{s}.

for some constant c that is uniform over all strings.

This normality criterion is quite useful because it means that instead of having to prove a precise asymptotic for the counting function on the left-hand side of (2), we need only know its value up to a constant multiple.

We will need another result on a sum of multinomial coefficients, which we present here. Define the set T_{ϵ} by

T_{ϵ} = {x = (x_{1}, …, x_{D}) ∈ ℝ^{D} | λ_{1}^{x_{1}}λ_{2}^{x_{2}} ⋯ λ_{D}^{x_{D}} ≥ ϵ, x_{i} ≥ 0, 1 ≤ i ≤ D} .

We will use m = (m_{1}, m_{2}, …, m_{D}) ∈ ℤ^{D} to denote an integer lattice point. Then define

S(ϵ) = ∑_{m∈T_{ϵ}}(m_{1} + m_{2} + ⋯ + m_{D})\frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}  (3)

and

S^{#}(ϵ) = ∑_{m∈T_{ϵ}} \frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}.  (4)

Theorem 5. We have

S(ϵ) ≍ \frac{| log ϵ|}{ϵ} S^{#}(ϵ) ≍ \frac{1}{ϵ}

as ϵ tends to 0.

The proof of Theorem 3 will be broken down into the following steps.

1. In Section 3, we shall apply a counting argument to express

#{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k}/N

in terms of the sums S(ϵ) and S^{#}(ϵ), so that Theorem 3 is a simple consequence of Theorem 5.

2. In Sections 4 and 5, we will show that the bounds in Theorem 5 follow from bounds on similar sums, where T_{ϵ} is replaced by a hyperplane segment

H_{ϵ} := {x = (x_{1}, x_{2}, …, x_{D}) | ∑_{i=1}^{D} x_{i} log λ_{i} = log ϵ, x_{i} ≥ 0, 1 ≤ i ≤ D} .

3. In Section 6, we analyze the size of the resulting sum over H_{ϵ} by applying the Laplace method (see [11] for more details).

In this paper we will frequently use the Landau and Vinogradov asymptotic notation, such as ≪, ≫, ≍, big-O, and little-o, all with the usual meanings.

2 Some additional results

We need a few general lemmas, which we will present here. Lemma 6. Let 1 < x < y and suppose that 0 < δ < min{1, x − 1}, then we have, uniformly in all variables

\frac{Γ(y − δ)}{Γ(x − δ)} ≪ \frac{Γ(y)}{Γ(x)} ≪ \frac{Γ(y + δ)}{Γ(x + δ)} and x ± δ ≍ x.

Proof. The first relation follows immediately from the fact that Γ(x + α) ≍ Γ(x)x^{α} provided x and x + α are on subset of the positive reals bounded away from 0. The second relation is trivial. Lemma 7. Let n be a positive integer, {p_{i}}_{i=1}^{n} be a set of real numbers, and {q_{i}}_{i=1}^{n} be a set of positive numbers. Then we have that

\frac{(∑_{i=1}^{n} p_{i})^{2}}{∑_{i=1}^{n} q_{i}} ≤ ∑_{i=1}^{n} \frac{p_{i}^{2}}{q_{i}} ,

with equality if and only if all the fractions {p_{i}/q_{i}}_{i=1}^{n} have the same value. Proof. This follows immediately from the Cauchy–Schwarz inequality:

(∑_{i=1}^{n} \sqrt{q_{i}} · \frac{p_{i}}{\sqrt{q_{i}}} )^{2} ≤ (∑_{i=1}^{n} \sqrt{q_{i}}^{2}) (∑_{i=1}^{n} (\frac{p_{i}}{\sqrt{q_{i}}} )^{2})

with equality if and only if there exists a constant C such that C\sqrt{q_{i}} = p_{i}/\sqrt{q_{i}}. Lemma 8. For a fixed constant C, we have

∑_{−Z^{2/3}≤k≤Z^{2/3}} exp (−\frac{C}{Z} k^{2}) = \sqrt{\frac{πZ}{C}} (1 + o(1))

as Z tends to ∞.

Proof. We apply Euler-Maclaurin summation:

∑_{−Z^{2/3}≤k≤Z^{2/3}} exp (−\frac{C}{Z} k^{2}) = ∫_{−Z^{2/3}}^{Z^{2/3}} exp (−\frac{C}{Z} x^{2}) dx

+ O (∫_{−Z^{2/3}}^{Z^{2/3}} \frac{C|x|}{Z} exp (−\frac{C}{Z} x^{2}) dx)

+ O (exp (−\frac{C}{Z} Z^{4/3}))

= \sqrt{\frac{πZ}{C}} − 2\sqrt{\frac{Z}{C}} · ∫_{Z^{1/6}C^{1/2}}^{∞} exp (−x^{2}) dx

+ O (∫_{0}^{Z^{1/6}C^{1/2}} |x| exp (−x^{2}) dx) + O (1)

= \sqrt{\frac{πZ}{C}} (1 + o(1)).

3 Proving Theorem 3 from Theorem 5

By Theorem 4, it suffices to show that for any string s = [a_{1}, a_{2}, …, a_{k}], we have

\frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} ≪ λ_{s},

with implicit constant uniform over all strings.

The counting function

#{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k}

is very difficult to compute directly, so we will instead estimate its size in terms of other, simpler functions. The Nth digit of x, d_{N}, must appear in the concatenation of some string s_{n}, for which we have μ(C[s_{n}]) = ϵ = ϵ(N).

Let A(ϵ; s) denote the number of time the string s occurs within the strings s_{i} where λ_{s_{i}} ≥ ϵ. Let A(ϵ) just denote the total number of digits in all the strings s_{i} where λ_{s_{i}} ≥ ϵ. We will also use A^{#}(ϵ) to denote the total number of strings s_{i} where λ_{s_{i}} ≥ ϵ.

With ϵ = ϵ(N), we clearly have

#{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k} ≤ A(ϵ; s) + kA^{#}(ϵ),

where the latter term comes from a trivial estimate on how many times the string s could occur starting in one string s_{i} and ending another string s_{j}. Moreover, the number N itself is at least A(2ϵ), and thus

\frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} ≤ \frac{A(ϵ; s) + kA^{#}(ϵ)}{A(2ϵ)}.

Now we wish to bound the A functions, in terms of the S functions (3) and (4). Following the assumption from Theorem 3, let us assume that for a string s = [a_{1}, a_{2}, …, a_{k}] we have

c_{1}λ_{a_{1}}λ_{a_{2}} ⋯ λ_{a_{k}} ≤ λ_{s} ≤ c_{2}λ_{a_{1}}λ_{a_{2}} ⋯ λ_{a_{k}}.

Suppose we want to count the total number of ways one can concatenate the string s together with m_{d} copies of the digit d. If counted with multiplicity, this will correctly count the total number of times s occurs in strings that have m_{d} + e_{d} copies of the digit d, where e_{d} is the number of times d occurs in s. There are precisely

(1 + m_{1} + m_{2} + ⋯ + m_{D}) · \frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}

such strings (counted with multiplicity), each of which will have a cylinder set of measure in the interval

[\frac{c_{1}}{c_{2}} λ_{s} · ∏_{d≤D} λ_{d}^{m_{d}}, \frac{c_{2}}{c_{1}} λ_{s} · ∏_{d≤D} λ_{d}^{m_{d}}] .

Thus if we let

S(ϵ; s) = ∑_{\begin{matrix}m_{1},m_{2},...,m_{D} \\ λ_{1}^{m_{1}}λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ/λ_{s} \end{matrix}}(1 + m_{1} + m_{2} + ⋯ + m_{D})\frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}

= S(ϵ/λ_{s}) + S^{#}(ϵ/λ_{s}),

then we clearly have

S (\frac{c_{2}}{c_{1}} ϵ; s) ≤ A(ϵ; s) ≤ S (\frac{c_{1}}{c_{2}} ϵ; s) .

By a similar argument we can show

S (\frac{c_{2}}{c_{1}} ϵ) ≤ A(ϵ) ≤ S (\frac{c_{1}}{c_{2}} ϵ) and S^{#} (\frac{c_{2}}{c_{1}} ϵ) ≤ A^{#}(ϵ) ≤ S^{#} (\frac{c_{1}}{c_{2}} ϵ) .

Thus,

\frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} ≤ \frac{S (\frac{c_{1}}{c_{2}λ_{s}} ϵ) + (k + 1)S^{#} (\frac{c_{1}}{c_{2}λ_{s}} ϵ)}{S (2\frac{c_{2}}{c_{1}} ϵ)}.

Now applying Theorem 5 we obtain

\frac{#\{0 ≤ n ≤ N − k | d_{n+i} = a_{i}, 1 ≤ i ≤ k\}}{N} ≪ \frac{(\frac{c_{1}}{c_{2}λ_{s}} ϵ)^{−1} |log (\frac{c_{1}}{c_{2}λ_{s}} ϵ)| + (k + 1) (\frac{c_{1}}{c_{2}λ_{s}} ϵ)^{−1}}{(2\frac{c_{2}}{c_{1}} ϵ)^{−1} |log (2\frac{c_{2}}{c_{1}} ϵ)|}

≪ λ_{s},

and these bounds are uniform in s, which completes the proof of Theorem 3.

4 Proof of Theorem 5

We will consider two new functions H(ϵ) and H^{#}(ϵ) given by the following.

Let H_{ϵ} denote the hyperplane segment

H_{ϵ} := {x = (x_{1}, x_{2}, …, x_{D}) | ∑_{i=1}^{D} x_{i} log λ_{i} = log ϵ, x_{i} ≥ 0, 1 ≤ i ≤ D} .

Note that

x_{1} log λ_{1}^{−1} + ⋯ + x_{D} log λ_{D}^{−1} ≤ log ϵ^{−1}

is equivalent to λ_{1}^{x_{1}} ⋯ λ_{D}^{x_{D}} ≥ ϵ. We will consider “lattice” points m ∈ H_{ϵ} to be given by (m_{1}, m_{2}, …, m_{D}) where m_{2}, …, m_{D} ∈ ℤ, and m_{1} = M is a real number determined by the other coordinates via the formula

M = \frac{log (ϵ/ (λ_{2}^{m_{2}}λ_{3}^{m_{3}} ⋯ λ_{D}^{m_{D}}))}{log λ_{1}}.

We then define H(ϵ) and H^{#}(ϵ) by

H(ϵ) := ∑_{m∈H_{ϵ}}(M + m_{2} + m_{3} + ⋯ + m_{D})\frac{(M + m_{2} + m_{3} + ⋯ + m_{D})!}{M!m_{2}!m_{3}! ⋯ m_{D}!}

H^{#}(ϵ) := ∑_{m∈H_{ϵ}} \frac{(M + m_{2} + m_{3} + ⋯ + m_{D})!}{M!m_{2}!m_{3}! ⋯ m_{D}!}

We extend the factorial to real values in the natural way by x! = Γ(x + 1).

While the functions S(ϵ) and S^{#}(ϵ) look at all values lying above the hyperplane H_{ϵ}, the functions H(ϵ) and H^{#}(ϵ) instead look at values on the hyperplane H_{ϵ}.

Theorem 5 (and therefore Theorem 3) will follow from the following two lemmas, which we prove in subsequent sections. Lemma 9. We have

H(ϵ/λ_{1}) ≪ S(ϵ) ≪ H(ϵ · λ_{2})  and  H^{#}(ϵ/λ_{1}) ≪ S^{#}(ϵ) ≪ H^{#}(ϵ · λ_{2}).

Lemma 10. We have

H(ϵ) ≍ \frac{| log ϵ|}{ϵ} H^{#}(ϵ) ≍ \frac{1}{ϵ}

as ϵ tends to 0.

5 Proof of Lemma 9

We shall provide bounds for S(ϵ). The method for S^{#}(ϵ) is similar.

First, we place a lower bound on S(ϵ). We have

S(ϵ) = ∑_{\begin{matrix}m_{2},...,m_{D} \\ λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}} (  ∑_{\begin{matrix}m_{1} \\ λ_{1}^{m_{1}}λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}}(m_{1} + m_{2} + ⋯ + m_{D})\frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!})

≫ ∑_{\begin{matrix}m_{2},...,m_{D} \\ λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}}(M′ + m_{2} + ⋯ + m_{D})\frac{(M′ + m_{2} + m_{3} + ⋯ + m_{D})!}{M′!m_{2}!m_{3}! ⋯ m_{D}!},

where in each summand M′ is the largest integer such that

λ_{1}^{M′}λ_{2}^{m_{2}}λ_{2}^{m_{3}} ⋯ λ_{D}^{m_{D}} ≥ ϵ.  (5)

Increasing the size of ϵ in the index of summation but not in the definition of M′ will only result in removing terms, therefore,

S(ϵ) ≫ ∑_{\begin{matrix}m_{2},...,m_{D} \\ λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ/λ_{1} \end{matrix}}(M′ + m_{2} + ⋯ + m_{D})\frac{(M′ + m_{2} + m_{3} + ⋯ + m_{D})!}{M′!m_{2}!m_{3}! ⋯ m_{D}!}.

Comparing this series term by term with H(ϵ/λ_{1}) and noting that M′ for this sum is greater than and within 1 of the corresponding M in the terms of H(ϵ/λ_{1}), we get that S(ϵ) ≫ H(ϵ/λ_{1}) by Lemma 6.

For the reverse inequality, we have, for fixed m_{2}, m_{3}, …, m_{D} and with M′ defined as in (5), that

∑_{\begin{matrix}m_{1} \\ λ_{1}^{m_{1}}λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}}(m_{1} + m_{2} + ⋯ + m_{D})\frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}

≤ (M′ + m_{2} + m_{3} + ⋯ + m_{D}) · ∑_{\begin{matrix}m_{1} \\ λ_{1}^{m_{1}}λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}} \frac{(m_{1} + m_{2} + ⋯ + m_{D})!}{m_{1}!m_{2}! ⋯ m_{D}!}

= (M′ + m_{2} + m_{3} + ⋯ + m_{D}) · \frac{(m_{2} + m_{3} + ⋯ + m_{D})!}{m_{2}!m_{3}! ⋯ m_{D}!}×

∑_{\begin{matrix}m_{1} \\ λ_{1}^{m_{1}}λ_{2}^{m_{2}}···λ_{D}^{m_{D}} ≥ϵ \end{matrix}} \binom{m_{1} + m_{2} + m_{3} + ⋯ + m_{D}}{m_{2} + m_{3} + ⋯ + m_{D}}

= (M′ + m_{2} + m_{3} + ⋯ + m_{D}) · \frac{(m_{2} + m_{3} + ⋯ + m_{D})!}{m_{2}!m_{3}! ⋯ m_{D}!}×

× \binom{M′ + 1 + m_{2} + m_{3} + ⋯ + m_{D}}{1 + m_{2} + m_{3} + ⋯ + m_{D}}

= \frac{m_{2} + 1}{1 + m_{2} + m_{3} + ⋯ + m_{D}} (M′ + m_{2} + m_{3} + ⋯ + m_{D})×

\binom{M′ + (m_{2} + 1) + m_{3} + m_{4} + ⋯ + m_{D}}{M, m_{2} + 1, m_{3}, m_{4}, …, m_{D}}

≪ (M′ + (m_{2} + 1) + m_{3} + ⋯ + m_{D}) · \frac{(M′ + (m_{2} + 1) + m_{3} + m_{4} + ⋯ + m_{D})!}{M!(m_{2} + 1)!m_{3}!m_{4}! ⋯ m_{D}!}.

By summing over all possible m_{2}, m_{3}, …, m_{D} for which the sum is non-empty, we obtain most of the terms from H(ϵ · λ_{2}), namely all the terms where m_{2} ≥ 1. So therefore we have S(ϵ) ≪ H(ϵ · λ_{2}).

6 Proof of Lemma 10

We shall provide the proof for H(ϵ), as the proof for H^{#}(ϵ) is similar.

We want to begin by examining the terms of H(ϵ), using Stirling’s formula. We will use a somewhat non-standard form as follows:

x! ≍ \sqrt{2π(x + 1)} (\frac{x}{e})^{x} .  (6)

This clearly follows from the usual Stirling’s formula for large x, since replacing x by x + 1 inside the square root introduces an error of at most 1 + O(x^{−1}); however this function has the added advantage of being true and uniform for all non-negative x, because the function on the right is bounded away from 0.

Now consider a given term of H(ϵ),

(M + m_{2} + m_{3} + ⋯ + m_{D})\frac{(M + m_{2} + m_{3} + ⋯ + m_{D})!}{M!m_{2}!m_{3}! ⋯ m_{D}!},  (7)

where, as before,

M = \frac{log (ϵ/ (λ_{2}^{m_{2}}λ_{3}^{m_{3}} ⋯ λ_{D}^{m_{D}}))}{log λ_{1}}.

Applying Stirling’s formula (6) gives that (7) is of the order of G(m) · exp (F (m)), where

G(m) := \frac{(M + m_{2} + ⋯ + m_{D} + 1)^{3/2}}{\sqrt{(M + 1)(m_{2} + 1)(m_{3} + 1) ⋯ (m_{D} + 1)}}

and

F (m) := (M + m_{2} + m_{3} + ⋯ + m_{D}) log(M + m_{2} + m_{3} + ⋯ + m_{D})

− M log M − ∑_{i=2}^{D} m_{i} log m_{i}.

The function G is fairly smooth and, compared to the exponential of F, quite small. Therefore we shall focus our studies primarily on understanding the properties of F.

6.1 Understanding F

In order to understand the properties of F better, it is helpful to work with an auxiliary function. Let

F̃(x) := (x_{1} + ⋯ + x_{D}) log(x_{1} + ⋯ + x_{D}) − ∑_{i=1}^{D} x_{i} log x_{i}

be a function on H_{ϵ}.

We think of F as being a function of D−1 variables. (The value of m_{1} = M is determined by the others.) However, we will think of F̃ as a function on D free variables, and then restrict our attention to the D − 1-dimensional hyperplane H_{ϵ}.

Proposition 11. Let l = (a_{1}t+b_{1}, a_{2}t+b_{2}, …, a_{D}t+b_{D}) be a line parallel to and intersecting the hyperplane segment H_{ϵ}. Then the second directional derivative of F̃ along this line is negative.

Proof. Since l is parallel to and intersecting H_{ϵ}, we have that

∑_{i=1}^{D}(a_{i}t + b_{i}) log λ_{i} = log ϵ.

By isolating the coefficient of t, we obtain

∑_{i=1}^{D} a_{i} log λ_{i} = 0.

In particular, since all the log λ_{i} are negative, there must exist at least one positive and one negative a_{i}.

The second derivative of F̃ along this line is given by

\frac{d^{2}}{dt^{2}} F̃(a_{1}t + b_{1}, …, a_{D}t + b_{D}) = \begin{matrix}(∑_{i=1}^{D} a_{i}) & 2 \\ ∑ & {D \atop i=1} & (a_{i}t + b_{i}) \end{matrix} − ∑_{i=1}^{D} \frac{a_{i}^{2}}{a_{i}t + b_{i}} .

By Lemma 7, this is never positive, and is zero if and only if a_{i}/(a_{i}t + b_{i}) has the same value for all i; however, in order to be in the domain of F̃, all the a_{i}t + b_{i} must be positive, and as we noted earlier, at least one m_{i} must be positive and at least one m_{i} must be negative, therefore the a_{i}/(a_{i}t + b_{i}) cannot all have the same value. The second derivative is therefore strictly negative.

This proposition produces two immediate consequences. First, F̃ must have a unique local maximum on H_{ϵ}: it must have a maximum on H_{ϵ} since it is a continuous function on a compact set, and there cannot be two local maximums since on the line between them F̃ would have strictly negative second derivative. Second, on any line passing through this maximum, the function F̃ is strictly decreasing away from the maximum.

Lemma 12. The function F̃(x) has its unique maximum on H_{ϵ} at the point p = (λ_{1}L, λ_{2}L, λ_{3}L, …, λ_{D}L), where

L = \frac{log(ϵ)}{λ_{1} log(λ_{1}) + λ_{2} log(λ_{2}) + ⋯ + λ_{D} log(λ_{D})}.

Moreover, F̃(p) = − log ϵ.

Proof. It is easy to see that p is on the hyperplane segment H_{ϵ}. Since all the directional second derivatives parallel to H_{ϵ} are negative, it suffices to show that, at the point p, all the directional first derivatives parallel to H_{ϵ} are 0.

As before, consider a line l(t) = (a_{1}t + λ_{1}L, …, a_{n}t + λ_{D}L) passing through the point p. We again have

∑_{i=1}^{D} a_{i} log λ_{i} = 0.

The directional derivative of F at p along this line (in the positive t direction) is given by

(∑_{i=1}^{D} a_{i}) log (∑_{i=1}^{D} λ_{i}L) − ∑_{i=1}^{D} (a_{i} log(λ_{i}L))

= (∑_{i=1}^{D} a_{i}) log (\frac{log(ϵ) ∑_{i=1}^{D} λ_{i}}{∑_{i=1}^{D} λ_{i} log λ_{i}} ) − ∑_{i=1}^{D} (a_{i} log (\frac{log(ϵ)λ_{i}}{∑_{j=1}^{D} λ_{j} log λ_{j}} ))

= (∑_{i=1}^{D} a_{i}) log (\frac{log(ϵ)}{∑_{i=1}^{D} λ_{i} log λ_{i}} ) − ∑_{i=1}^{D} (a_{i} log (\frac{log(ϵ)}{∑_{j=1}^{D} λ_{j} log λ_{j}} ))

− ∑_{i=1}^{D} a_{i} log λ_{i}

= 0.

This shows that p is the maximum. The value F̃ takes at this point is given by

(∑_{i=1}^{D} λ_{i}L) log (∑_{i=1}^{D} λ_{i}L) − ∑_{i=1}^{D} λ_{i}L log(λ_{i}L)

= \frac{log ϵ}{∑_{j=1}^{D} λ_{j} log λ_{j}} log (\frac{log ϵ}{∑_{j=1}^{D} λ_{j} log λ_{j}} )

− ∑_{i=1}^{D} \frac{λ_{i} log ϵ}{∑_{j=1}^{D} λ_{j} log λ_{j}} log (\frac{λ_{i} log ϵ}{∑_{j=1}^{D} λ_{j} log λ_{j}} )

= − ∑_{i=1}^{D} \frac{λ_{i} log ϵ}{∑_{j=1}^{D} λ_{j} log λ_{j}} log λ_{i}

= − log ϵ,

which completes the proof.

We will abuse notation and consider x ∈ H_{ϵ} as being both the vector (x_{1}, x_{2}, …, x_{D}) and the vector (x_{2}, …, x_{D}) with implied extra variable

x_{1} = \frac{1}{log λ_{1}} (log ϵ − ∑_{i=2}^{n} x_{i} log λ_{i}) .

And likewise we will consider p ∈ H_{ϵ} as being both the vector (λ_{1}L, λ_{2}L, …, λ_{D}L) and the vector (λ_{2}L, λ_{3}L, …, λ_{D}L).

Therefore F can be given by

F (x) = (\frac{log ϵ}{log λ_{1}} + ∑_{i=2}^{D} x_{i} (1 − \frac{log λ_{i}}{log λ_{1}} )) log (\frac{log ϵ}{log λ_{1}} + ∑_{i=2}^{D} x_{i} (1 − \frac{log λ_{i}}{log λ_{1}} ))

− (\frac{log ϵ}{log λ_{1}} − ∑_{i=2}^{D} x_{i} \frac{log λ_{i}}{log λ_{1}} ) log (\frac{log ϵ}{log λ_{1}} − ∑_{i=2}^{D} x_{i} \frac{log λ_{i}}{log λ_{1}} )

− ∑_{i=2}^{D} x_{i} log x_{i}.

Given 2 ≤ i, j ≤ D, we have

\frac{∂^{2}}{∂x_{i}∂x_{j}} F (x) = \frac{(1 − \frac{log λ_{i}}{log λ_{1}} ) (1 − \frac{log λ_{j}}{log λ_{1}} )}{\frac{log ϵ}{log λ_{1}} + ∑_{i=2}^{D} x_{i} (1 − \frac{log λ_{i}}{log λ_{1}} )}

− \frac{\frac{log λ_{i} log λ_{j}}{(log λ_{1})^{2}}}{\frac{log ϵ}{log λ_{1}} − ∑_{i=2}^{D} x_{i} \frac{log λ_{i}}{log λ_{1}}} − \frac{δ_{i,j}}{x_{i}} .

So, if we consider the second partial derivatives at p arranged in a matrix, then we see that there exists a fixed real symmetric matrix A (independent of ϵ), such that

\frac{∂^{2}}{∂x_{i}∂x_{j}} F (p) = \frac{1}{log ϵ}A_{i−1,j−1}.

Since (log ϵ)^{−1}A is a real symmetric matrix, it can be diagonalized by orthogonal matrices. In particular, this implies that there exist unit vectors u_{2}, u_{3}, …, u_{D} ∈ ℝ^{D−1} and fixed eigenvalues l_{2}, l_{3}, …, l_{D} (again not dependent on ϵ) such that

\frac{∂^{2}}{∂u_{i}∂u_{j}} F (p) = \begin{cases}\frac{l_{j}}{log ϵ}, & if i = j; \\ 0, & otherwise. \end{cases}

By Proposition 11 the second directional derivatives must always be negative, so l_{j} must be positive.

Consider a ball B_{ϵ} around the point p, given by

B_{ϵ} = {p + t_{2}u_{2} + ⋯ + t_{D}u_{D} | ∑_{i=2}^{D} t_{i}^{2} ≤ | log ϵ|^{2/3}} .

Note that for sufficiently small ϵ, we have B_{ϵ} ⊂ H_{ϵ}. We also consider a box B_{ϵ} given by

B_{ϵ} = \{p + t_{2}e_{2} + ⋯ + t_{D}e_{D} | |t_{i}| ≤ \frac{1}{\sqrt{D − 1}}| log ϵ|^{2/3}\} ,

where e_{i} are the elementary basis vectors. We have that B_{ϵ} ⊂ B_{ϵ}.

If x ∈ B_{ϵ}, then each coordinate x_{i} of x must be on the order of | log x|. Therefore for all points x ∈ B_{ϵ}, the third partial derivative of F satisfies the following bound:

\frac{∂^{3}}{∂u_{j}∂u_{D}∂u_{l}} F (x) ≪ | log ϵ|^{−2}.

By Taylor’s Theorem, for any point x = p + t_{2}u_{2} + ⋯ + t_{D}u_{D} ∈ B_{ϵ}, we have

F (x) = − log ϵ + ∑_{i=2}^{D} \frac{l_{i}}{log ϵ}t_{i}^{2} + O(1).  (8)

Let F_{+} and F_{−} be given by

F_{+}(x) = − log ϵ + ( max_{2≤i≤D} \frac{l_{i}}{log ϵ}) ∑_{i=2}^{D} t_{i}^{2}

and

F_{−}(x) = − log ϵ + ( min_{2≤i≤D} \frac{l_{i}}{log ϵ}) ∑_{i=2}^{D} t_{i}^{2},

so that

F_{−}(x) ≤ F (x) + O(1) ≤ F_{+}(x).

These functions are advantageous because ∑_{j=2}^{D} t_{j}^{2} is invariant under rotation around p. If x = p + y_{2}e_{2} + ⋯ + y_{D}e_{D} is in the box B_{ϵ}, then

F_{+}(x) = − log ϵ + ( max_{2≤i≤n} \frac{l_{i}}{log ϵ}) ∑_{i=2}^{n} y_{i}^{2},

and likewise for F_{−}.

Moreover, for each point x outside of the box B_{ϵ}, we can draw a line between x and p and note that by Lemma 12, F increases along the line as we move towards p. Therefore, the value of F at x ∉ B_{ϵ} is at most the maximum of F on the boundary of B_{ϵ}, and by (8), this is at most − log ϵ − C| log ϵ|^{1/3} for some fixed positive constant C.

6.2 Returning to the full sum

For points x ∈ B_{ϵ}, it is easy to see that G(x) is on the order of | log ϵ|^{(3−D)/2} and for x ∉ B_{ϵ}, the value G(x) could be as large as | log ϵ|. Therefore,

∑_{m∈H_{ϵ}\B_{ϵ}} G(m) exp(F (m)) ≪ ∑_{m∈H_{ϵ}\B_{ϵ}} | log ϵ| exp(− log ϵ − C| log ϵ|^{1/3})
≪ | log ϵ|^{D} exp(− log ϵ − C| log ϵ|^{1/3}) = o(ϵ^{−1}).

Here we used the fact that m_{i} ≪ | log ϵ|.

Therefore

H(ϵ) ≍ ∑_{m∈B_{ϵ}} G(m) exp(F (m)) + o(ϵ^{−1}).

Since, as noted above G(m) is on the order of | log ϵ|^{(3−D)/2} for m ∈ B_{ϵ}, to complete the proof it suffices to prove that

∑_{m∈B_{ϵ}} exp(F (m)) ≍ \frac{| log ϵ|^{D−1}}{ϵ} .

First we note that

∑_{m∈B_{ϵ}} exp(F_{−}(m)) ≪ ∑_{m∈B_{ϵ}} exp(F (m)) ≪ ∑_{m∈B_{ϵ}} exp(F_{+}(m)).

There exists a point p′ within distance \sqrt{D − 1}/2 from p, such that p′ is an integer lattice point. For m ∈ B_{ϵ}, let m′ = m + p − p′. Then we have F_{±}(m) − F_{±}(m′) = O(| log ϵ|^{−1/3}) = O(1). Moreover, each vector m′ can be written as p + k_{2}e_{2} + ⋯ + k_{D}e_{D} ∈ B_{ϵ} with each k_{i} in the interval

I = [−c| log ϵ|^{2/3} − \frac{\sqrt{D − 1}}{2}, c| log ϵ|^{2/3} + \frac{\sqrt{D − 1}}{2}] .

Therefore

∑_{m∈B_{ϵ}} exp(F_{+}(m)) ≍ ∑_{m∈B_{ϵ}} exp(F_{+}(m + p − p′))  (9)

≤ \frac{1}{ϵ} ∏_{i=2}^{D} (∑_{k_{i}∈I} exp (( max_{2≤i≤D} \frac{l_{i}}{log ϵ}) k_{i}^{2})) ,  (10)

and likewise

∑_{m∈B_{ϵ}} exp(F_{−}(m)) ≫ \frac{1}{ϵ} ∏_{i=2}^{D} (∑_{k_{i}∈J} exp (( max_{2≤i≤D} \frac{l_{i}}{log ϵ}) k_{i}^{2})) ,  (11)

where

J = [−c| log ϵ|^{2/3} + \frac{\sqrt{D − 1}}{2}, c| log ϵ|^{2/3} − \frac{\sqrt{D − 1}}{2}] .

Applying Lemma 8 to (10) and (11) completes the proof.

References

[1] C. Altomare and B. Mance, Cantor series constructions contrasting two notions of normality, Monatsh. Math., 164 (2011), 1–22.

[2] David H. Bailey and Richard E. Crandall, On the random character of fundamental constant expansions, Experiment. Math., 10 (2001), 175–190.

[3] David H. Bailey and Richard E. Crandall, Random generators and normal numbers, Experiment. Math., 11 (2003), 527–546.

[4] David H. Bailey and Michał Misiurewicz, A strong hot spot theorem, Proc. Amer. Math. Soc., 134 (2006), 2495–2501.

[5] Barat et al., Dynamical directions in numeration, Ann. Inst. Fourier (Grenoble), 56 (2006), 1987–2092.

[6] Anne Bertrand-Mathis and Bodo Volkmann, On (ϵ, k)-normal words in connecting dynamical systems, Monats. Math., 107 (1989), 267–279.

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

[8] Arthur H. Copeland and Paul Erdős, Note on normal numbers, Bull. Amer. Math. Soc., 52 (1946), 857–860.

[9] Karma Dajani and Cor Kraaikamp, Ergodic Theory of Numbers, volume 29 of Carus Mathematical Monographs. Mathematical Association of America, 2002.

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

[11] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover Publications Inc., 1981.

[12] M. Madritsch and B. Mance, Construction of μ-normal sequences, preprint,

    http://arxiv.org/abs/1206.4950.

[13] Bill Mance, Construction of normal numbers with respect to the Q-Cantor series expansion for certain Q, Acta Arith., 148 (2011), 135–152.

[14] Bill Mance, Cantor series constructions of sets of normal numbers, Acta Arith., 156 (2012), 223–245.

[15] F. J. Martinelli, Construction of generalized normal numbers, Pacific J. Math., 76 (1978), 117–122.

[16] N. G. Moshchevitin and I. D. Shkredov, On the Pyatetskiĭ-Shapiro criterion for normality, Mat. Zametki, 73 (2003), 577–589.

[17] Fritz Schweiger, Ergodic Theory of Fibred Systems and Metric Number Theory, Oxford Science Publications, 1995.

2010 Mathematics Subject Classification: Primary 11K16. Keywords: normal number, multinomial coefficient.

Received December 20 2013; revised versions received March 29 2014; April 9 2014. Published in Journal of Integer Sequences, April 15 2014.

Return to Journal of Integer Sequences home page.