\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
A Simpler Normal Number Construction for \\
\vskip .1in
Simple L\"uroth Series
}
\vskip 1cm
\large
J. Vandehey\\
University of Georgia at Athens \\
Department of Mathematics\\
Athens, GA 30602 \\
USA\\
\href{mailto:vandehey@uga.edu}{\tt vandehey@uga.edu}
\end{center}
\vskip .2 in
\newcommand{\x}{\mathbf{x}}
\newcommand{\uu}{\mathbf{u}}
\newcommand{\p}{\mathbf{p}}
\newcommand{\m}{\mathbf{m}}
\begin{abstract}
Champernowne famously proved that the number \[0.(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)\cdots\] 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\"uroth 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.
\end{abstract}
\section{Introduction}
A number $x\in [0,1)$ with base $b$ expansion $x=0.d_1d_2d_3\cdots$ is said to be normal to base $b$ if for any string $s=a_1 a_2\cdots a_k$ of base $b$ digits, we have
\[
\lim_{N\to \infty} \frac{\#\{ 0 \le n \le N\mid d_{n+i} = a_i, \quad 1 \le i \le 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\in [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 $\pi$, 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 \cite{Champernowne}, which in base $10$ looks like
\[
0.(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)\cdots,
\]
formed by concatenating all the integers in succession. He derived this construction after proving the base $10$ normality of the following number
\begin{equation}\label{eq:champernowne}
0.(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(00)(01)(02)(03)\cdots,
\end{equation}
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\H{o}s \cite{CE}, that is perhaps the most natural generalization of Champernowne's techniques; the exponential sum method first introduced by Davenport and Erd\H{o}s \cite{DE}; and the method of pseudo-random number generators used most powerfully by Bailey and Crandall \cite{BC1,BC2}.
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\H{o}s. We shall be concerned here with ergodic fibred systems \cite{Barat,Schweiger}. Common examples of fibred systems include base $b$ expansions, continued fraction expansions, generalized L\"{u}roth series, and $\beta$-expansions.
\begin{definition}Ergodic fibred systems consist with a transformation $T$ that maps a set $\Omega$ to itself, a measure $\mu$ on $\Omega$ that is finite and $T$-invariant, a digit set $\mathcal{D}\subset\mathbb{N}$, and a countable collection of disjoint subsets $\{I_d\}_{d\in \mathcal{D}}$ such that every point in $\Omega$ is in some $I_d$. The map $T$ is injective on each subset $I_d$ and $T$ is ergodic with respect to $\mu$, \emph{i.e.}, for every $A\subset \Omega$ with $T^{-1} A=A$ (up to some set of $\mu$-measure $0$), either $\mu(A)=0$ or $\mu(A)=1$.
The $T$-expansion of a point $x\in \Omega$ is then given by $x=[d_1,d_2,d_3,\ldots]$ where $d_n$ is defined by $T^{n-1}x \in I_{d_n}$.\footnote{Our definitions here, in particular the part where $\{I_d\}_{d\in \mathcal{D}}$ form a partition of $\Omega$, are somewhat nonstandard, but they guarantee that these expansions always exist and are unique for a given $x$.} For a given fibred system, we say a point $x\in\Omega$ with expansion $x=[d_1, d_2, d_3, \ldots]$ is $T$-normal if for any string $s=[a_1, a_2, \ldots, a_k]$ of digits from $\mathcal{D}$ we have
\begin{equation}\label{eq:mainlimit}
\lim_{N\to \infty} \frac{\#\{ 0 \le n \le N-k\mid d_{n+i} = a_i, \quad 1 \le i \le k\}}{N} = \mu(C[s]).
\end{equation}
where $C[s]$ is the cylinder set for the string $s$, i.e.,
\[
C[s]= \{x=[d_1, d_2, \ldots] \mid d_i=a_i, \quad 1\le i \le k\}.
\]
We will often denote the measure of a cylinder set $s$ by $\lambda_s$, and if $s$ consists of a single digit $d$, then we will often shorthand the measure of the set $C[d]$ by $\lambda_d$.
\end{definition}
We will denote the number of digits in the digit set $\mathcal{D}$ by $D$, and often assume that $\mathcal{D}=\{1,2,\ldots,D\}$.
Madritsch and Mance \cite{MM} recently provided a normal number construction that works for many ergodic fibred systems, including those listed above. Their construction works roughly as follows:
\begin{enumerate}
\item Let $\epsilon_k$ be some small positive number shrinking to $0$ very quickly as $k$ increases, and let $S_k=\{s_1, s_2, s_3, \ldots, s_n\}$ be a set enumerating all strings of length $k$ whose corresponding cylinder sets have measure at least $\epsilon_k$.
\item Let $M_k$ be at least $1/\epsilon_k$, and construct a string $X_k$ formed by concatenating first $\lfloor M_k \lambda_{s_1}\rfloor$ copies of $s_1$, then $\lfloor M_k \lambda_{s_2} \rfloor$ copies of $s_2$ and so on until ending with $\lfloor M_k \lambda_{s_n} \rfloor$ 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.
\item 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.
\end{enumerate}
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 \cite{AM}, and Mance \cite{M2,M1} independently. The construction also bears resemblence to an earlier, but less general construction of Martinelli \cite{Martinelli}, 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 $\beta$-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 \eqref{eq:champernowne}, 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 \cite{BMV}, 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\"uroth 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.
\begin{definition}\label{defn:xs}
Given an ergodic fibred system, let $S= \{s_n\}_{n\in \mathbb{N}}$ be an enumeration of all possible finite length strings ordered according to the following rule:
If $\lambda_{s_i} > \lambda_{s_j}$, then $i