# A $p$-Adic Characterization of the Periodic Points of a Class of Collatz-
Type Maps on the Integers

Maxwell C. Siegel

(Wednesday, June 30, 2021)

###### Abstract

Fix an integer $\varrho\geq 2$. We consider maps
$H:\mathbb{Z}\rightarrow\mathbb{Z}$ so that for any $n\in\mathbb{Z}$, the
value of $H\left(n\right)$ is the image of one of $\varrho$ distinct affine-
linear maps, the choice of which is determined by the value of $n$ mod
$\varrho$; these maps generalize the infamous Collatz or $3x+1$ map. This
paper introduces a $p$-adic formalism for studying the sets of periodic points
of $H$, applicable to the case where $H$ is the Collatz map, as well as a
large family of generalizations thereof. When applicable, this approach yields
a function $\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q}$ (where $q$
is an integer $\geq 2$ associated to $H$ and where $q$ is an integer depending
on $H$) with the property that every element of
$\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\mathbb{Z}$ is a periodic point
of $\chi_{H}$, and that every cycle of $H$ of length $\geq 2$ contains an
element of $\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\mathbb{Z}$. The
$\chi_{H}$ formalism simplifies, unifies, and generalizes previous work by
other authors on Collatz-type maps (both old and recent), and establishes a
foundation for future work on the periodic points of Collatz-type maps using
methods of $p$-adic Fourier analysis, Complex analysis, and Probability
theory.

Keywords: Collatz Conjecture, $p$-adic numbers, $p$-adic Fourier analysis,
parity vector, $3x+1$ map, $5x+1$ map, Catalan’s Conjecture.

This research did not receive any specific grant from funding agencies in the
public, commercial, or not-for-profit sectors.

University of Southern California, Dornsife School of Letters & Sciences,
Department of Mathematics.

Department of Mathematics 3620 S. Vermont Ave., KAP 104, Los Angeles, CA
90089-2532.

E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
ORCID: 0000-0002-7746-2874

## Introduction

Fix an integer $\varrho\geq 2$. This paper is concerned with maps
$H:\mathbb{Z}\rightarrow\mathbb{Z}$ expressible in the form:

$H\left(n\right)=\begin{cases}\frac{a_{0}n+b_{0}}{d_{0}}&\textrm{if
}n=0\mod\varrho\\\ \frac{a_{1}n+b_{1}}{d_{1}}&\textrm{if }n=1\mod\varrho\\\
\vdots&\vdots\\\ \frac{a_{\varrho-1}n+b_{\varrho-1}}{d_{\varrho}}&\textrm{if
}n=\varrho-1\mod\varrho\end{cases},\textrm{ }\forall n\in\mathbb{Z}$ (1)

where $a_{j}$, $b_{j}$, and $d_{j}$ are integer constants (with
$a_{j},d_{j}\geq 0$ for all $j$) so that the following two properties hold:

I. (“co-primality”) $a_{j},d_{j}>0$ and $\gcd\left(a_{j},d_{j}\right)=1$ for
all $j\in\left\\{0,\ldots,\varrho-1\right\\}$.

II. (“integrality”) For each $j\in\left\\{0,\ldots,\varrho-1\right\\}$,
$\frac{a_{j}n+b_{j}}{d_{j}}$ is a non-negative integer if and only if
$n=j\mod\varrho$.

Maps of this type generalize the Collatz map:

$C\left(n\right)\overset{\textrm{def}}{=}\begin{cases}\frac{n}{2}&\textrm{if
}n=0\mod 2\\\ 3n+1&\textrm{if }n=1\mod 2\end{cases}$ (2)

as well as various generalizations thereof, such as the shortened $ax+1$ maps
(where $a$ is an odd integer $\geq 3$):

$T_{a}\left(n\right)\overset{\textrm{def}}{=}\begin{cases}\frac{n}{2}&\textrm{if
}n=0\mod 2\\\ \frac{an+1}{2}&\textrm{if }n=1\mod 2\end{cases}$ (3)

(see, for instance, [7], which studies $T_{3}$ and $T_{5}$), $n$-furcations
(considered by [5]), $\left(f,g,h\right)$-maps (considered by [8]), and many
of the myriad examples studied by K.R. Matthews and his colleagues (see [14,
11, 10, 12, 13]). These maps can also be generalized to rings other than
$\mathbb{Z}$, such as the ring of integers of an algebraic number field (see
[13] for examples), although we shall reserve a study of this particular
generalization for a later publication.

Definition: We say $H$ is semi-basic whenever the following conditions hold:

i. $H\left(0\right)=0$.

ii. (“non-degenerate”) $a_{j}\neq 1$ for all non-zero $j$.

iii. (“monogenic111This term is based on the Greek for “one kind/species”.”)
The constant:

$q_{H}\overset{\textrm{def}}{=}\gcd\left(\left\\{a_{j}:j\in\left\\{0,\ldots,\varrho-1\right\\}\textrm{
\& }a_{j}\neq 1\right\\}\right)$ (4)

is $\geq 2$. For compactness, we will sometimes write $q$ instead of $q_{H}$.

iv. (“semi-simple”) $\gcd\left(a_{j},d_{k}\right)=1$ for all
$j,k\in\left\\{0,\ldots,\varrho-1\right\\}$.

Alternatively, we say that $H$ is basic if $H$ satisfies (i), (ii), and (iii),
as well as the condition:

v. (“simple”) $d_{j}=\varrho$ for all $j$.

Note here that (v) implies (iv), so every basic $H$ is also semi-basic, though
the converse is not true.

The principle results of this paper are as follows:

Theorem I (Characterization and extension of $\chi_{H}$): Let $H$ be semi-
basic. Then:

I. There is a unique function $\chi_{H}:\mathbb{N}_{0}\rightarrow\mathbb{Q}$
(where, for any $k\in\mathbb{R}$, $\mathbb{N}_{k}$ denotes the set of all
integers $\geq k$) which satisfies the system of functional equations:

$\chi_{H}\left(\varrho
n+j\right)=\frac{a_{j}\chi_{H}\left(n\right)+b_{j}}{d_{j}},\textrm{ }\forall
j\in\left\\{0,\ldots,\varrho-1\right\\},\textrm{ }\forall n\in\mathbb{N}_{0}$
(5)

II. The function $\chi_{H}$ characterized by (5) admits a unique extension to
a function $\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q_{H}}$, with:

$\chi_{H}\left(\mathfrak{z}\right)\overset{\mathbb{Z}_{q_{H}}}{=}\lim_{n\rightarrow\infty}\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{n}}\right),\textrm{
}\forall\mathfrak{z}\in\mathbb{Z}_{\varrho}$ (6)

where $\overset{\mathbb{Z}_{q_{H}}}{=}$ emphasizes the fact that the limit in
(6) occurs in $\mathbb{Z}_{q_{H}}$; here,
$\left[\mathfrak{z}\right]_{\varrho^{n}}$ denotes the value of the
$\varrho$-adic integer222We utilize $\mathfrak{fraktur}$ font (\mathfrak) to
denote non-archimedean quantities. modulo $\varrho^{n}$—that is, the unique
integer in $\left\\{0,\ldots,\varrho^{n}-1\right\\}$ which is congruent to
$\mathfrak{z}$ mod $\varrho^{n}$. This extension is continuous on
$\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$, the set of all $\varrho$-adic
integers which are not non-negative rational integers.

III. The extension of $\chi_{H}$ given by (6) satisfies the system of
functional equations:

$\chi_{H}\left(\varrho\mathfrak{z}+j\right)=\frac{a_{j}\chi_{H}\left(\mathfrak{z}\right)+b_{j}}{d_{j}},\textrm{
}\forall j\in\left\\{0,\ldots,\varrho-1\right\\},\textrm{
}\forall\mathfrak{z}\in\mathbb{Z}_{\varrho}$ (7)

Moreover, the extension of $\chi_{H}$ given by (6) is the unique
$\mathbb{Z}_{q_{H}}$-valued function on $\mathbb{Z}_{\varrho}$ satisfying (7).

Theorem II (“The Correspondence Theorem”): If $H$ is basic, then the following
are true:

I. $\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\Omega\neq\varnothing$ for
any cycle $\Omega\subseteq\mathbb{Z}$ of $H$ with $\left|\Omega\right|\geq 2$
(i.e., $\Omega$ contains at least two elements). We make sense of this
intersection by viewing both $\chi_{H}\left(\mathbb{Z}_{\varrho}\right)$ and
$\Omega$ as having been embedded in $\mathbb{Z}_{q_{H}}$.

II. Every element of $\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\mathbb{Z}$
is a periodic point of $H$.

With $\chi_{H}$, the problem of determining the periodic points of any basic
$H$ is reduced to understanding the possible rational-integer values attained
by $\chi_{H}$ over $\mathbb{Z}_{\varrho}$. The $\chi_{H}$ formalism also
yields generalizations of “cycle-generating formulas” (see [5]), such as the
following classic formula of Böhm and Sontacchi[2]:

The Böhm-Sontacchi Criterion333This name is non-standard, and is the author’s
invention.: Let $x\in\mathbb{Z}$ be a periodic point of the Collatz map $C$
(2). Then, there are integers $m,n\geq 1$ and a strictly increasing sequence
of positive integers $b_{1}<b_{2}<\cdots<b_{n}$ so that:

$x=\frac{\sum_{k=1}^{n}2^{m-b_{k}-1}3^{k-1}}{2^{m}-3^{n}}$ (8)

Generalizing this result follows from realizing it as a specific case of a
more general functional equation satisfied by $\chi_{H}$. Through this
functional equation, we obtain an explicit parameterization of the quantities
$m$, $n$, and $b_{1},\ldots,b_{n}$ (and their corresponding generalizations
for other $H$s) in terms of a single positive-integer-valued parameter. As
will be discussed in the paper’s conclusion, this sets the stage for
applications of classical techniques in complex analysis and $p$-adic Fourier
analysis to further study the periodic points of $H$.

## Declarations

Funding: None.

Conflicts of interest/Competing interests: None.

Availability of data and material: Not applicable

Code availability: Not applicable

## Results

##  1 Notation and Preliminary Definitions

1 - Definition (the branches of $H$): For each
$j\in\left\\{0,\ldots,\varrho-1\right\\}$, we write
$H_{j}:\mathbb{R}\rightarrow\mathbb{R}$ to denote the $j$th branch of $H$,
defined as the function:

$H_{j}\left(x\right)\overset{\textrm{def}}{=}\frac{a_{j}x+b_{j}}{d_{j}}$ (9)

_NOTE_ :__ in our study, _it is imperative that_ _$b_{0}=0$_ , _so as to
guarantee that_ _ $H\left(0\right)=0$_. Consequently, we will have that
$H\left(0\right)=H_{0}\left(0\right)=0$.

Next, as a consequence of (1), observe that for all $m\in\mathbb{N}_{0}$ and
all $j\in\left\\{0,\ldots,\varrho-1\right\\}$, we can write:

$\underbrace{H\left(\varrho
m+j\right)}_{\in\mathbb{N}_{0}}=\frac{a_{j}\left(\varrho
m+j\right)+b_{j}}{d_{j}}=\frac{\varrho
a_{j}m}{d_{j}}+\frac{ja_{j}+b_{j}}{d_{j}}=\frac{\varrho
a_{j}}{d_{j}}m+\underbrace{H\left(j\right)}_{\in\mathbb{N}_{0}}$

Setting $m=1$, we see that the quantity $\frac{\varrho
a_{j}}{d_{j}}=H\left(\varrho m+j\right)-H\left(j\right)$ must be an integer
for each value of $j$. This quantity occurs often enough in computations that
it deserves its own symbol:

2 - Definition ($\mu_{j}$): We write $\mu_{j}$ to denote:

$\mu_{j}\overset{\textrm{def}}{=}\frac{\varrho
a_{j}}{d_{j}}\in\mathbb{N}_{1},\textrm{ }\forall
j\in\left\\{0,\ldots,\varrho-1\right\\}$ (10)

In particular, since $a_{j}$ and $d_{j}$ are always co-prime, note that
$d_{j}$ must be a divisor of $\varrho$. When $H$ is basic, $\varrho=d_{j}$,
and as such, we have $\mu_{j}=a_{j}$ for all $j$.

_Remark_ : With this notation, we then have that:

$H\left(\varrho m+j\right)=\mu_{j}m+H\left(j\right),\textrm{ }\forall
m\in\mathbb{Z},\textrm{ }\forall j\in\left\\{0,\ldots,\varrho-1\right\\}$ (11)

Our next definitions concern our notation for sequences of
$\left\\{0,\ldots,\varrho-1\right\\}$.

3 - Definition (Strings and composition sequences): For each
$n\in\mathbb{N}_{1}$, let $\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{n}$
denote the set of all $n$-tuples whose entries are elements of the set
$\left\\{0,\ldots,\varrho-1\right\\}$. We denote an arbitrary such tuple as
$\mathbf{j}=\left(j_{1},\ldots,j_{n}\right)$, and we say $\mathbf{j}$ is non-
zero if $\mathbf{j}$ contains at least one non-zero entry. Given any such
tuple, we write $\left|\mathbf{j}\right|$ to denote the length of
$\mathbf{j}$. In this manner, any $\mathbf{j}$ can be written as
$\mathbf{j}=\left(j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)$.

Next, to denote the set of all tuples of finite length, we write:

$\textrm{String}\left(\varrho\right)\overset{\textrm{def}}{=}\bigcup_{n=1}^{\infty}\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{n}$
(12)

Given any $\mathbf{j}\in\textrm{String}\left(\varrho\right)$, we define the
composition sequence $H_{\mathbf{j}}:\mathbb{R}\rightarrow\mathbb{R}$ as the
affine linear map:

$H_{\mathbf{j}}\left(x\right)=\left(H_{j_{1}}\circ\cdots\circ
H_{j_{\left|\mathbf{j}\right|}}\right)\left(x\right),\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (13)

When writing by hand, one can use vector notation instead of bold-face:
$H_{\vec{j}}$, instead of $H_{\mathbf{j}}$.

With this notation, we can describe the motivation for the paper and the
methods we shall use. The idea is to consider what happens to
$H_{\mathbf{j}}\left(x\right)$ as we allow
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ to vary. First off, since
the $H_{j}$s are affine linear maps, the same will be true of any composition
sequence thereof. In particular, we can write $H_{\mathbf{j}}\left(x\right)$
in $ax+b$ form as:

$H_{\mathbf{j}}\left(x\right)=H_{\mathbf{j}}^{\prime}\left(0\right)x+H_{\mathbf{j}}\left(0\right),\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (14)

If $\mathbf{j}$ is a string for which $H_{\mathbf{j}}\left(x\right)=x$, this
becomes:

$x=H_{\mathbf{j}}^{\prime}\left(0\right)x+H_{\mathbf{j}}\left(0\right)$ (15)

from which we obtain:

$x=\frac{H_{\mathbf{j}}\left(0\right)}{1-H_{\mathbf{j}}^{\prime}\left(0\right)}$
(16)

In this manner, given any $\mathbf{j}$, we can solve for the unique rational
number $x$ which is left fixed by $H_{\mathbf{j}}$. The one-to-one
correspondence between $\mathbf{j}$ and $x$ appears to have been first noticed
by [5], who refer to it as the Bijection Theorem. We shall go one step
further, however, and obtain (16) in the form of a functional equation
satisfied by $\chi_{H}$. (15), meanwhile, is what motivates the realization of
$\chi_{H}$ as a function on $\mathbb{Z}_{\varrho}$. We shall prove that $H$
being semi-basic is exactly the condition needed in order to guarantee that,
for fixed $x$, the right-hand side of (15) will converge in
$\mathbb{Z}_{q_{H}}$ to $H_{\mathbf{j}}\left(0\right)$ as
$\left|\mathbf{j}\right|\rightarrow\infty$, provided that, as
$\left|\mathbf{j}\right|\rightarrow\infty$, the number of non-zero entries in
$\mathbf{j}$ increases to $\infty$ as well. By identifying strings
$\mathbf{j}$ of finite length with the sequence of $\varrho$-adic digits of
non-negative integers, we can then identify infinitely long $\mathbf{j}$s with
$\varrho$-adic integers, whereupon we obtain an extension of $\chi_{H}$, first
defined as a function on $\mathbb{N}_{0}$, to one defined on
$\mathbb{Z}_{\varrho}$. Our next definition gives the details behind these
identifications.

4 - Definition (Identifying strings with non-negative integers;
concatenation): Given
$\mathbf{j}=\left(j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)\in\textrm{String}\left(\varrho\right)$
and $n\in\mathbb{N}_{0}$, we say $\mathbf{j}$ represents (or is associated to)
$n$ (and vice-versa), written $\mathbf{j}\sim n$ or $n\sim\mathbf{j}$,
whenever $\mathbf{j}$ is the sequence of the $\varrho$-adic digits of $n$;
that is:

$n\sim\mathbf{j}\Leftrightarrow\mathbf{j}\sim n\Leftrightarrow
n=j_{1}+j_{2}\varrho+j_{3}\varrho^{2}+\cdots+j_{\left|\mathbf{j}\right|}\varrho^{\left|\mathbf{j}\right|-1}$
(17)

As defined, for any given $n$, note that there are infinitely many
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ which represent $n$. Given
any such $\mathbf{j}$, one can obtain another such $\mathbf{j}$ by
concatenating $0$s to the right of $\mathbf{j}$. As such, in a minor abuse of
notation, we will use $\sim$ to indicate that two strings $\mathbf{i}$ and
$\mathbf{j}$ represent the same rational integer:

$\mathbf{i}\sim\mathbf{j}\Leftrightarrow\mathbf{i}\textrm{ and
}\mathbf{j}\textrm{ represent the same rational integer}$

This makes $\sim$ into an equivalence relation on
$\textrm{String}\left(\varrho\right)$. We write
$\textrm{String}\left(\varrho\right)/\sim$ to denote the set
$\textrm{String}\left(\varrho\right)=\bigcup_{n=1}^{\infty}\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{n}$
under this equivalence relation.

Next, we write $\textrm{String}_{\infty}\left(\varrho\right)$ to denote the
set of all tuples
$\mathbf{j}=\left(j_{1},j_{2},\ldots\right)\in\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{\mathbb{N}_{1}}$
of infinite length. Given a $\varrho$-adic integer $\mathfrak{z}$, in one more
abuse of notation, we then write $\mathbf{j}\sim\mathfrak{z}$ and
$\mathfrak{z}\sim\mathbf{j}$ to extend (17) to include $\varrho$-adic
integers. $\textrm{String}_{\infty}\left(\varrho\right)/\sim$ denotes the set
of equivalence classes of $\textrm{String}_{\infty}\left(\varrho\right)$ under
the relation:

$\mathbf{i}\sim\mathbf{j}\Leftrightarrow\mathbf{i}\textrm{ and
}\mathbf{j}\textrm{ represent the same $\varrho$-adic integer}$

and we have that $\textrm{String}_{\infty}\left(\varrho\right)/\sim$ is then
in a bijective correspondence with $\mathbb{Z}_{\varrho}$.

We also introduce the concatenation operator
$\wedge:\textrm{String}\left(\varrho\right)\times\textrm{String}\left(\varrho\right)\rightarrow\textrm{String}\left(\varrho\right)$,
defined by:

$\mathbf{i}\wedge\mathbf{j}=\left(i_{1},\ldots,i_{\left|\mathbf{i}\right|}\right)\wedge\left(j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)\overset{\textrm{def}}{=}\left(i_{1},\ldots,i_{\left|\mathbf{i}\right|},j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)$
(18)

We extend the concatenation operator notation in the obvious way to allow
ourselves to write $\mathbf{i}\wedge\mathbf{j}$ where $\mathbf{i}$ has finite
length and $\mathbf{j}$ has infinite length. Finally, for any integer $m\geq
1$, we write $\mathbf{j}^{\wedge m}$ to denote the concatenation of $m$ copies
of $\mathbf{j}$:

$\mathbf{j}^{\wedge
m}\overset{\textrm{def}}{=}\left(\underbrace{j_{1},\ldots,j_{\left|\mathbf{j}\right|},j_{1},\ldots,j_{\left|\mathbf{j}\right|},\ldots,j_{1},\ldots,j_{\left|\mathbf{j}\right|}}_{m\textrm{
times}}\right)$

We shall only use this notation when $\mathbf{j}$ has finite length.

By and by, we will show that the formula (16) is the general form of cycle-
generating formula such as (8). To that end, by way of our identification of
$\mathbf{j}$s with non-negative integers $n$, we will be able to parameterize
the right-hand side of (16) in terms of the $n$, with the parameterization
being governed by the properties of the $\varrho$-adic digits of $n$. We will
keep trakc of these properties using the following arithmetic functions:

5 - Definition (the functions444Since there is no consistent standard in the
literature for these functions, the author here utilizes his own notation.
$\lambda_{\varrho}$ and
$\\#_{\varrho:0},\\#_{\varrho:1},\ldots,\\#_{\varrho:\varrho-1}$): We write
$\lambda_{\varrho}:\mathbb{N}_{0}\rightarrow\mathbb{N}_{0}$ to denote the
function:

$\lambda_{\varrho}\left(n\right)\overset{\textrm{def}}{=}\left\lceil\log_{\varrho}\left(n+1\right)\right\rceil,\textrm{
}\forall n\in\mathbb{N}_{0}$ (19)

which gives the number of $\varrho$-adic digits of $n$. Note then, that every
$n\in\mathbb{N}_{0}$ can be uniquely written as:

$n=c_{0}+c_{1}\varrho+\cdots+c_{\lambda_{\varrho}\left(n\right)-1}\varrho^{\lambda_{\varrho}\left(n\right)-1}$

where the $c_{j}$s are integers in $\left\\{0,\ldots,\varrho-1\right\\}$; in
particular, if $n\sim\mathbf{j}$, then
$\lambda_{\varrho}\left(n\right)\leq\left|\mathbf{j}\right|$. Additionally,
note that:

$\left\lceil\log_{\varrho}\left(n+1\right)\right\rceil=\left\lfloor\log_{\varrho}n\right\rfloor+1,\textrm{
}\forall n\in\mathbb{N}_{1}$ (20)

Next, for each $n\geq 1$ and each $k\in\left\\{0,\ldots,\varrho-1\right\\}$,
we write $\\#_{\varrho:k}\left(n\right)$ to denote the number of $k$s present
in the $\varrho$-adic expansion of $n$; that is,
$\\#_{\varrho:k}\left(n\right)$ is the number of $\varrho$-adic digits of $n$
which are equal to $k$. We define $\\#_{\varrho:k}\left(0\right)$ to be $0$
for all $k$.

As an example, for:

$n=2\cdot 3^{0}+0\cdot 3^{1}+2\cdot 3^{2}=20$

we have:

$\displaystyle\\#_{3:0}\left(20\right)$ $\displaystyle=1$
$\displaystyle\\#_{3:1}\left(20\right)$ $\displaystyle=0$
$\displaystyle\\#_{3:2}\left(20\right)$ $\displaystyle=2$

In an abuse of notation, we also use this notation to denote the number of
particular entries in a given tuple:

$\\#_{\varrho:k}\left(\mathbf{j}\right)\overset{\textrm{def}}{=}\textrm{number
of }k\textrm{s in }\mathbf{j},\textrm{ }\forall
k\in\mathbb{Z}/\varrho\mathbb{Z},\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (21)

where, as we do throughout the paper, we always __ identify
$\mathbb{Z}/\varrho\mathbb{Z}$ with the set
$\left\\{0,\ldots,\varrho-1\right\\}$.

6 - Proposition (Functional equations for $\lambda_{\varrho}$ and the
$\\#_{\varrho:k}$s):

$\displaystyle\\#_{\varrho:k}\left(\varrho^{n}a+b\right)$
$\displaystyle=\\#_{\varrho:k}\left(a\right)+\\#_{\varrho:k}\left(b\right),\textrm{
}\forall a\in\mathbb{N}_{0},\textrm{ }\forall n\in\mathbb{N}_{1},\textrm{
}\forall b\in\left\\{0,\ldots,\varrho^{n}-1\right\\}$ (22)
$\displaystyle\lambda_{\varrho}\left(\varrho^{n}a+b\right)$
$\displaystyle=\lambda_{\varrho}\left(a\right)+n,\textrm{ }\forall
a\in\mathbb{N}_{1},\textrm{ }\forall n\in\mathbb{N}_{1},\textrm{ }\forall
b\in\left\\{0,\ldots,\varrho^{n}-1\right\\}$ (23)
$\sum_{k=0}^{\varrho-1}\\#_{\varrho:k}\left(n\right)=\lambda_{\varrho}\left(n\right)$
(24)

_Remark_ : $\mathbb{N}_{1}$ denotes the set of all integers $\geq 1$.

Proof: A straightforward computation.

Q.E.D.

##  2 $\chi_{H}$ and the Correspondence Theorem

We begin by defining $\chi_{H}$ on $\mathbb{N}_{0}$ (the set of integers $\geq
0$)

7 - Definition ($\chi_{H}$ on $\mathbb{N}_{0}$): Let $H$ be any map of the
form (1) that fixes $0$. Then:

I. For any $\mathbf{j}\in\textrm{String}\left(\varrho\right)$, we write:

$\chi_{H}\left(\mathbf{j}\right)\overset{\textrm{def}}{=}H_{\mathbf{j}}\left(0\right)$
(25)

II. For any integer $n\geq 1$, we write:

$\chi_{H}\left(n\right)\overset{\textrm{def}}{=}\chi_{H}\left(\mathbf{j}\right)=H_{\mathbf{j}}\left(0\right)$
(26)

where $\mathbf{j}$ is any element of $\textrm{String}\left(\varrho\right)$
which represents $n$.

III. We define $\chi_{H}\left(0\right)\overset{\textrm{def}}{=}0$.

_Remark_ : Note that $\chi_{H}$ is then a well-defined function from
$\textrm{String}\left(\varrho\right)/\sim$ (equivalently, $\mathbb{N}_{0}$) to
$\mathbb{Q}$. Indeed, since $H\left(0\right)=H_{0}\left(0\right)=0$, we have
that:

$j_{m}=0\Rightarrow
H_{\left(j_{1},\ldots,j_{m}\right)}\left(0\right)=H_{\left(j_{1},\ldots,j_{m-1}\right)}\left(0\right)$

As such, if $\mathbf{i}$ and $\mathbf{j}$ are two tuples that represent the
same non-negative integer $n$, it must be that $\mathbf{i}$ can be obtained by
either adding or deleting $0$s to the right of $\mathbf{j}$, and hence:

$H_{\mathbf{i}}\left(0\right)=H_{\mathbf{j}}\left(0\right)$

Thus, the value of (26) is defined independently of the choice of string
$\mathbf{j}$ used to represent $n$.

8 - Definition ($M_{H}$): We define
$M_{H}:\mathbb{N}_{0}\rightarrow\mathbb{N}_{0}$ by:

$M_{H}\left(n\right)\overset{\textrm{def}}{=}M_{H}\left(\mathbf{j}\right)\overset{\textrm{def}}{=}H_{\mathbf{j}}^{\prime}\left(0\right),\textrm{
}\forall n\geq 1$ (27)

where $\mathbf{j}\in\textrm{String}\left(\varrho\right)$ is the sequence of
$\varrho$-adic digits of $n$; that is, $\mathbf{j}$ is the shortest element of
$\textrm{String}\left(\varrho\right)$ which represents $n$. By definition, we
write $M_{H}\left(0\right)\overset{\textrm{def}}{=}1$.

_Remarks_ :

I. Unlike $\chi_{H}$, $M_{H}$ is _not necessarily well-defined over_
$\textrm{String}\left(\varrho\right)/\sim$; there can be $H$ and distinct
strings $\mathbf{i},\mathbf{j}\in\textrm{String}\left(\varrho\right)$ with
$\mathbf{i}\sim\mathbf{j}$, and yet $M_{H}\left(\mathbf{i}\right)\neq
M_{H}\left(\mathbf{j}\right)$. For example, letting $H=T_{3}$, we have that
the strings $\left(0,1\right)$ and $\left(0,1,0\right)$ both represent the
integer $2$, and yet:

$\displaystyle H_{0,1}\left(x\right)$
$\displaystyle=H_{0}\left(H_{1}\left(x\right)\right)=\frac{3}{4}x+\frac{1}{4}$
$\displaystyle H_{0,1,0}\left(x\right)$
$\displaystyle=H_{0}\left(H_{1}\left(H_{0}\left(x\right)\right)\right)=\frac{3}{8}x+\frac{1}{4}$

Thus, $\left(0,1\right)\sim\left(0,1,0\right)$, yet
$M_{T_{3}}\left(0,1\right)=3/4$ and $M_{T_{3}}\left(0,1,0\right)=3/8$ are not
the same.

II. $M_{H}\left(n\right)$ and $M_{H}\left(\mathbf{j}\right)$ can be explicitly
given in terms of the constants associated to $H$ by the formulae:

$M_{H}\left(n\right)=\frac{1}{\varrho^{\lambda_{\varrho}\left(n\right)}}\prod_{k=0}^{\varrho-1}\mu_{k}^{\\#_{\varrho:k}\left(n\right)}=\prod_{k=0}^{\varrho-1}\frac{a_{k}^{\\#_{\varrho:k}\left(n\right)}}{d_{k}^{\\#_{\varrho:k}\left(n\right)}}$
(28)

and:

$M_{H}\left(\mathbf{j}\right)=\prod_{k=1}^{\left|\mathbf{j}\right|}\frac{a_{j_{k}}}{d_{j_{k}}}=\frac{1}{\varrho^{\left|\mathbf{j}\right|}}\prod_{k=1}^{\left|\mathbf{j}\right|}\mu_{j_{k}}=\frac{1}{\varrho^{\left|\mathbf{j}\right|}}\prod_{k=0}^{\varrho-1}\mu_{k}^{\\#_{\varrho:k}\left(\mathbf{j}\right)}=\prod_{k=0}^{\varrho-1}\frac{a_{k}^{\\#_{\varrho:k}\left(\mathbf{j}\right)}}{d_{k}^{\\#_{\varrho:k}\left(\mathbf{j}\right)}}$
(29)

respectively. We adopt the convention that the $k$-product in (29) is defined
to be $1$ when $\left|\mathbf{j}\right|=0$.

9 - Proposition (Formula for $\chi_{H}\left(\mathbf{j}\right)$):

$\chi_{H}\left(\mathbf{j}\right)=\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}=\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{a_{j_{m}}}\left(\prod_{k=1}^{m}\mu_{j_{k}}\right)\varrho^{-m},\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (30)

where the $k$-product is defined to be $1$ when $m=1$.

Proof: Let
$\mathbf{j}=\left(j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)\in\textrm{String}\left(\varrho\right)$
be arbitrary. Since
$\chi_{H}\left(\mathbf{j}\right)=\chi_{H}\left(\mathbf{i}\right)$ for any
$\mathbf{i}\in\textrm{String}\left(\varrho\right)$ for which
$\mathbf{i}\sim\mathbf{j}$, we can assume without loss of generality that
$\mathbf{j}$’s right-most entry is non-zero; that is:
$j_{\left|\mathbf{j}\right|}\neq 0$. Now, we can write the affine map
$H_{\mathbf{j}}$ as:

$H_{\mathbf{j}}\left(x\right)=H_{\mathbf{j}}^{\prime}\left(0\right)x+H_{\mathbf{j}}\left(0\right)=H_{\mathbf{j}}^{\prime}\left(0\right)x+\chi_{H}\left(\mathbf{j}\right),\textrm{
}\forall x\in\mathbb{R}$

Carefully writing out the composition sequence in the above equation yields
the first of our desired formulae:

$H_{\mathbf{j}}\left(x\right)=\frac{a_{j_{1}}\frac{a_{j_{2}}\left(\cdots\right)+b_{j_{2}}}{d_{j_{2}}}+b_{j_{1}}}{d_{j_{1}}}=M_{H}\left(\mathbf{j}\right)x+\underbrace{\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}}_{\chi_{H}\left(\mathbf{j}\right)}$
(31)

where our convention is that $\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}=1$
when $m=1$. This proves:

$\chi_{H}\left(\mathbf{j}\right)=\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}$

Re-writing this using $\mu_{j}=\frac{\varrho a_{j}}{d_{j}}$, we obtain:

$\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}=\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{a_{j_{m}}}\left(\prod_{k=1}^{m}\mu_{j_{k}}\right)\varrho^{-m}$

which proves the proposition.

Q.E.D.

10 - Proposition (Expression for $H_{\mathbf{j}}$):

$H_{\mathbf{j}}\left(x\right)=M_{H}\left(\mathbf{j}\right)x+\chi_{H}\left(\mathbf{j}\right),\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right),\textrm{ }\forall
x\in\mathbb{R}$ (32)

Proof: This was shown in (31) in the proof of item 9.

Q.E.D.

Next, we obtain systems of functional equations which characterize $M_{H}$ and
$\chi_{H}$, respectively.

11 - Proposition ($M_{H}$’s Functional Equations):

$M_{H}\left(\varrho
n+j\right)=\frac{\mu_{j}}{\varrho}M_{H}\left(n\right),\textrm{ }\forall n\geq
0\textrm{ \& }\forall j\in\mathbb{Z}/\varrho\mathbb{Z}:\varrho n+j\neq 0$ (33)

_Remark_ : The reader should take care to note that (33) does _not_ hold when
$\varrho n+j=0$.

Proof: Let $n\geq 0$, and let $\mathbf{j}=\left(j_{1},\ldots,j_{m}\right)$ be
the shortest string in $\textrm{String}\left(\varrho\right)$ which represents
$n$. Then, observe that for any $j_{m+1}\in\mathbb{Z}/\varrho\mathbb{Z}$, the
integer $\varrho n+j_{m+1}$ is then represented by the string
$\left(j_{1},\ldots,j_{m},j_{m+1}\right)$ , which we can obtained from
$\mathbf{j}$ by appending $j_{m+1}$ to the right of $\mathbf{j}$. As such, by
(29):

$M_{H}\left(\varrho
n+j_{m+1}\right)=\prod_{k=1}^{m+1}\frac{a_{j_{k}}}{d_{j_{k}}}=\frac{a_{j_{m+1}}}{d_{j_{m+1}}}M_{H}\left(\mathbf{j}\right)=\frac{\mu_{j_{m+1}}}{\varrho}M_{H}\left(n\right)$

Q.E.D.

At present, we have a means of interpreting $\chi_{H}$ as a rational-valued
function on $\mathbb{N}_{0}$, the set of non-negative integers. We now
establish the system of functional equations that uniquely characterize
$\chi_{H}$. Afterward, we will interpolate $\chi_{H}$ to a $q_{H}$-adic valued
function over $\mathbb{Z}_{\varrho}$, and show that this interpolation, when
it exists, is unique and also satisfies the system of functional equations
described below.

12 - Lemma ($\chi_{H}$’s Functional Equations): $\chi_{H}$ is the unique
rational-valued function on $\mathbb{N}_{0}$ satisfying the system of
functional equations:

$\chi_{H}\left(\varrho
n+j\right)=\frac{a_{j}\chi_{H}\left(n\right)+b_{j}}{d_{j}},\textrm{ }\forall
n\in\mathbb{N}_{0},\textrm{ }\forall j\in\left\\{0,\ldots,\varrho-1\right\\}$
(34)

Note that this can be written more compactly as:

$\chi_{H}\left(\varrho
n+j\right)=H_{j}\left(\chi_{H}\left(n\right)\right),\textrm{ }\forall
n\in\mathbb{N}_{0},\textrm{ }\forall j\in\left\\{0,\ldots,\varrho-1\right\\}$
(35)

Proof: We see that
$\chi_{H}\left(0\right)=H_{0}\left(\chi_{H}\left(0\right)\right)$ which is
true, since $\chi_{H}\left(0\right)=0$ and
$H\left(0\right)=H_{0}\left(0\right)=0$. So, let $N\geq 1$, and let $N=\varrho
n+j_{0}$. Letting
$\mathbf{j}=\left(j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)$ represent
$n$ we have that:

$\mathbf{i}\overset{\textrm{def}}{=}\left(i_{1},\ldots,i_{\left|\mathbf{i}\right|}\right)\overset{\textrm{def}}{=}\left(j_{0},j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)$

then represents $N$. As such, by (30):

$\chi_{H}\left(\varrho
n+j_{0}\right)=\chi_{H}\left(\mathbf{i}\right)=\sum_{m=1}^{\left|\mathbf{i}\right|}\frac{b_{i_{m}}}{d_{i_{m}}}\prod_{k=1}^{m-1}\frac{a_{i_{k}}}{d_{i_{k}}}=\sum_{m=1}^{\left|\mathbf{j}\right|+1}\frac{b_{j_{m-1}}}{d_{j_{m-1}}}\prod_{k=1}^{m-1}\frac{a_{j_{k-1}}}{d_{j_{k-1}}}$

Re-indexing the expression on the far right gives:

$\chi_{H}\left(\varrho
n+j_{0}\right)=\sum_{m=0}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=0}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}=\frac{b_{j_{0}}}{d_{j_{0}}}+\frac{a_{j_{0}}}{d_{j_{0}}}\overbrace{\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}}}^{\chi_{H}\left(\mathbf{j}\right)}$

Since $\mathbf{j}\sim n$, we can then write:

$\chi_{H}\left(\varrho
n+j_{0}\right)=\frac{b_{j_{0}}}{d_{j_{0}}}+\frac{a_{j_{0}}}{d_{j_{0}}}\chi_{H}\left(n\right)=\frac{a_{j_{0}}\chi_{H}\left(n\right)+b_{j_{0}}}{d_{j_{0}}}=H_{j_{0}}\left(n\right)$

Consequently, $\chi_{H}$ is _a_ solution of the system (34).

To see that $\chi_{H}$ is the _only_ possible solution of (34), suppose let
$f:\mathbb{N}_{0}\rightarrow\mathbb{C}$ be a function satisfying:

$f\left(\varrho n+j\right)=H_{j}\left(f\left(n\right)\right),\textrm{ }\forall
n\geq 0,\textrm{ }\forall j\in\left\\{0,\ldots,\varrho-1\right\\}$ (36)

Now, letting $n=j=0$, we have that
$f\left(0\right)=H_{0}\left(f\left(0\right)\right)$, which forces
$f\left(0\right)=0$. Next, we claim the following:

Claim: Let $f:\mathbb{N}_{0}\rightarrow\mathbb{C}$ satisfy (36). Then:

$f\left(\varrho^{m}n+i_{1}+i_{2}\varrho+\cdots+i_{m}\varrho^{m-1}\right)=H_{\mathbf{i}}\left(f\left(n\right)\right)$
(37)

for all
$\mathbf{i}=\left(i_{1},\ldots,i_{m}\right)\in\textrm{String}\left(\varrho\right)$,
all $m\geq 1$, and all $n\in\mathbb{N}_{0}$. More generally, we have that:

$f\left(\mathbf{i}\wedge\mathbf{j}\right)=H_{\mathbf{i}}\left(f\left(\mathbf{j}\right)\right),\textrm{
}\forall\mathbf{i},\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (38)

Proof of Claim: By induction, we see that:

$\displaystyle f\left(\varrho n+j_{1}\right)$
$\displaystyle=H_{j_{1}}\left(f\left(n\right)\right)$ $\displaystyle
f\left(\varrho\left(\varrho n+j_{2}\right)+j_{1}\right)$
$\displaystyle=H_{j_{1}}\left(f\left(\varrho
n+j_{2}\right)\right)=H_{j_{1}}\left(H_{j_{2}}\left(f\left(n\right)\right)\right)$
$\displaystyle\vdots$

which proves (37). The concatenation identity (38) follows from the
observation that, for $\mathbf{i}$ and $\mathbf{j}$, letting $k\sim\mathbf{i}$
and $n\sim\mathbf{j}$:

$\displaystyle\mathbf{i}\wedge\mathbf{j}$ $\displaystyle\sim
i_{1}+i_{2}\varrho+i_{3}\varrho^{2}+\cdots+i_{\left|\mathbf{i}\right|}\varrho^{\left|\mathbf{i}\right|-1}+j_{1}\varrho^{\left|\mathbf{i}\right|}+j_{2}\varrho^{\left|\mathbf{i}\right|+1}+\cdots+j_{\left|\mathbf{j}\right|}\varrho^{\left|\mathbf{i}\right|+\left|\mathbf{j}\right|-1}$
$\displaystyle=\underbrace{i_{1}+i_{2}\varrho+i_{3}\varrho^{2}+\cdots+i_{\left|\mathbf{i}\right|}\varrho^{\left|\mathbf{i}\right|-1}}_{k}+\varrho^{\left|\mathbf{i}\right|}\underbrace{\left(j_{1}+j_{2}\varrho+\cdots+j_{\left|\mathbf{j}\right|}\varrho^{\left|\mathbf{j}\right|-1}\right)}_{n}$
$\displaystyle=\varrho^{\left|\mathbf{i}\right|}n+k$

whereupon we can apply (37) to obtain:

$\displaystyle f\left(\mathbf{i}\wedge\mathbf{j}\right)$
$\displaystyle=f\left(\varrho^{\left|\mathbf{i}\right|}n+k\right)$
$\displaystyle=f\left(\varrho^{\left|\mathbf{i}\right|}n+i_{1}+i_{2}\varrho+i_{3}\varrho^{2}+\cdots+i_{\left|\mathbf{i}\right|}\varrho^{\left|\mathbf{i}\right|-1}\right)$
$\displaystyle=H_{\mathbf{i}}\left(f\left(n\right)\right)$
$\displaystyle\left(n\sim\mathbf{j}\right);$
$\displaystyle=H_{\mathbf{i}}\left(f\left(\mathbf{j}\right)\right)$

(38). This proves the Claim. $\checkmark$

Setting $n=0$ in (36) gives:

$f\left(\mathbf{i}\right)=f\left(0+i_{1}+i_{2}\varrho+\cdots+i_{m}\varrho^{m-1}\right)=H_{\mathbf{i}}\left(f\left(0\right)\right)=H_{\mathbf{i}}\left(0\right)=\chi_{H}\left(\mathbf{i}\right)$

Since $\mathbf{i}\in\textrm{String}\left(\varrho\right)$ was arbitrary, we
conclude that $f=\chi_{H}$, as desired.

Q.E.D.

$M_{H}$ also satisfies an analogue of (37):

13 - Proposition: Let
$\mathbf{i}=\left(i_{1},i_{2},\ldots,i_{m}\right)\in\textrm{String}\left(\varrho\right)$,
where $m\geq 1$. Then:

$M_{H}\left(\varrho^{m}n+i_{1}+i_{2}\varrho+\cdots+i_{m}\varrho^{m-1}\right)=M_{H}\left(\mathbf{i}\right)M_{H}\left(n\right)$
(39)

In particular:

$M_{H}\left(\mathbf{i}\wedge\mathbf{j}\right)=M_{H}\left(\mathbf{i}\right)M_{H}\left(\mathbf{j}\right),\textrm{
}\forall\mathbf{i},\mathbf{j}\in\textrm{String}\left(\varrho\right),\textrm{
}\left|\mathbf{i}\right|,\left|\mathbf{j}\right|\geq 1$ (40)

Proof: By induction on (33):

$\displaystyle M_{H}\left(\varrho n+i_{1}\right)$
$\displaystyle=\frac{\mu_{i_{1}}}{\varrho}M_{H}\left(n\right)=\frac{a_{i_{1}}}{d_{i_{1}}}M_{H}\left(n\right)$
$\displaystyle M_{H}\left(\varrho\left(\varrho n+i_{2}\right)+i_{1}\right)$
$\displaystyle=\frac{a_{i_{1}}}{d_{i_{1}}}M_{H}\left(\varrho
n+i_{2}\right)=\frac{a_{i_{1}}}{d_{i_{1}}}\frac{a_{i_{2}}}{d_{i_{2}}}M_{H}\left(n\right)$
$\displaystyle\vdots$

we see that (39) is true. The concatenation identity (40) follows by noting
that for $\mathbf{i},\mathbf{j}\in\textrm{String}\left(\varrho\right)$ and
$\mathbf{v}\overset{\textrm{def}}{=}\mathbf{i}\wedge\mathbf{j}=\left(i_{1},\ldots,i_{\left|\mathbf{i}\right|},j_{1},\ldots,j_{\left|\mathbf{j}\right|}\right)\overset{\textrm{def}}{=}\left(v_{1},v_{2},\ldots,v_{\left|\mathbf{v}\right|}\right)$
(where
$\left|\mathbf{v}\right|=\left|\mathbf{i}\right|+\left|\mathbf{j}\right|$):

$M_{H}\left(\mathbf{i}\wedge\mathbf{j}\right)=\prod_{k=1}^{\left|\mathbf{v}\right|}\frac{a_{v_{k}}}{d_{v_{k}}}=\prod_{k=1}^{\left|\mathbf{i}\right|}\frac{a_{v_{k}}}{d_{v_{k}}}\cdot\prod_{\ell=\left|\mathbf{i}\right|+1}^{\left|\mathbf{i}\right|+\left|\mathbf{j}\right|}\frac{a_{v_{\ell}}}{d_{v_{\ell}}}=\prod_{k=1}^{\left|\mathbf{i}\right|}\frac{a_{i_{k}}}{d_{i_{k}}}\cdot\prod_{k=1}^{\left|\mathbf{j}\right|}\frac{a_{j_{\ell}}}{d_{j_{\ell}}}=M_{H}\left(\mathbf{i}\right)M_{H}\left(\mathbf{j}\right)$

Q.E.D.

Next, we characterize the $q_{H}$-adic behavior of $M_{H}$ in preparation for
interpolating $\chi_{H}$ from a rational-valued function on $\mathbb{N}_{0}$
to a $q_{H}$-adic-valued function on $\mathbb{Z}_{\varrho}$. It is worth
noting that the conditions required for $\chi_{H}$’s interpolation to exist
(semi-basicness) are less restrictive than the conditions required for the
Correspondence Theorem to hold (basicness), which is shown in the following
elementary proposition.

15 - Proposition (Co-primality of $d_{j}$ and $q_{H}$): Let $H$ be semi-basic.
Then, $\gcd\left(d_{j},q_{H}\right)=1$ for all
$j\in\left\\{0,\ldots,\varrho-1\right\\}$.

Proof: By way of contradiction, suppose there is a
$k\in\left\\{0,\ldots,\varrho-1\right\\}$ so that
$\gcd\left(d_{k},q_{H}\right)>1$. Since $H$ is semi-basic, $q_{H}$ is $\geq 2$
and, moreover, $a_{j}\neq 1$ for any
$j\in\left\\{1,\ldots,\varrho-1\right\\}$. Thus, there is a $k$ so that
$d_{k}$ and $q_{H}$ have a non-trivial common factor, and there is a $j$ so
that $q_{H}$ and $a_{j}$ have a non-trivial common factor (namely, $q_{H}$).
Since every factor of $q_{H}$ divides $a_{j}$, the non-trivial common factor
of $d_{k}$ and $q_{H}$ must also divide $a_{j}$, which forces
$\gcd\left(a_{j},d_{k}\right)>1$. However, since $H$ is semi-basic,
$\gcd\left(a_{j},d_{k}\right)=1$ for all
$j,k\in\left\\{0,\ldots,\varrho-1\right\\}$. This is a contradiction!

Thus, it must be that $\gcd\left(d_{k},q_{H}\right)=1$ for all
$k\in\left\\{0,\ldots,\varrho-1\right\\}$.

Q.E.D.

Now comes our description of the $q_{H}$-adic behavior of $M_{H}$.

16 - Proposition ($q_{H}$-adic behavior of $M_{H}\left(\mathbf{j}\right)$ as
$\left|\mathbf{j}\right|\rightarrow\infty$): Let $H$ be semi-basic. For
brevity, write $q=q_{H}$, and let
$\nu_{q}:\mathbb{Q}_{q}\rightarrow\mathbb{Z}\cup\left\\{\infty\right\\}$
denote the $q$-adic valuation map (so that
$\left|n\right|_{q}=q^{-\nu_{q}\left(n\right)}$, with
$\nu_{q}\left(0\right)\overset{\textrm{def}}{=}+\infty$). Then, the following
inequality holds for all non-zero
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$:

$\nu_{q}\left(M_{H}\left(\mathbf{j}\right)\right)\geq\sum_{k=1}^{\varrho-1}\\#_{\varrho:k}\left(\mathbf{j}\right)=\left|\mathbf{j}\right|-\\#_{\varrho:0}\left(\mathbf{j}\right)$
(41)

_Remark_ :__ Since
$\sum_{k=1}^{\varrho-1}\\#_{\varrho:k}\left(\mathbf{j}\right)=\left|\mathbf{j}\right|-\\#_{\varrho:0}\left(\mathbf{j}\right)$
is the number of non-zero digits of $\mathbf{j}$, this proposition can simply
be stated as: _$\nu_{q}\left(M_{H}\left(\mathbf{j}\right)\right)$ is greater
than or equal to the number of non-zero entries in _$\mathbf{j}$. Furthermore,
since
$\left|M_{H}\left(\mathbf{j}\right)\right|_{q}=q^{-\nu_{q}\left(M_{H}\left(\mathbf{j}\right)\right)}$,
(41) shows that $\left|M_{H}\left(\mathbf{j}\right)\right|_{q}$ decreases as
the number of non-zero entries of $\mathbf{j}$ increases, with
$\left|M_{H}\left(\mathbf{j}\right)\right|_{q}$ tending to $0$ as the number
of non-zero entries of $\mathbf{j}$ tends to $\infty$.

Proof: Let $\mathbf{j}$ be a non-zero element of
$\textrm{String}\left(\varrho\right)$. Then, by (29):

$M_{H}\left(\mathbf{j}\right)=\prod_{\ell=1}^{\left|\mathbf{j}\right|}\frac{a_{j_{\ell}}}{d_{j_{\ell}}}$

and so, by the multiplication-to-addition homomorphism property of the
$q$-adic valuation $\nu_{q}$, we can write:

$\nu_{q}\left(M_{H}\left(\mathbf{j}\right)\right)=\sum_{\ell=1}^{\left|\mathbf{j}\right|}\nu_{q}\left(a_{j_{\ell}}\right)-\sum_{\ell=1}^{\left|\mathbf{j}\right|}\nu_{q}\left(d_{j_{\ell}}\right)$
(42)

Since $H$ is semi-basic, 15 tells us that every $d_{j}$ is co-prime to $q$; as
such, $\nu_{q}\left(d_{j}\right)=0$ for any value of $j$. On the other hand,
$H$ being semi-basic means that $a_{j}$ is a non-zero integer multiple of $q$
for all non-zero $j$; thus, $\nu_{q}\left(a_{j_{\ell}}\right)\geq 1$ for every
$\ell$ for which $j_{\ell}\neq 0$. So, letting
$N=\sum_{k=1}^{\varrho-1}\\#_{\varrho:k}\left(\mathbf{j}\right)=\left|\mathbf{j}\right|-\\#_{\varrho:0}\left(\mathbf{j}\right)$
denote the number of non-zero entries of $\mathbf{j}$, our previous equation
becomes:

$\nu_{q}\left(M_{H}\left(\mathbf{j}\right)\right)=\sum_{\ell=1}^{\left|\mathbf{j}\right|}\nu_{q}\left(a_{j_{\ell}}\right)-\overbrace{\sum_{\ell=1}^{\left|\mathbf{j}\right|}\nu_{q}\left(d_{j_{\ell}}\right)}^{0}\geq
N$

because $\nu_{q}\left(a_{j_{\ell}}\right)\geq 1$ occurs for each non-zero
$j_{\ell}$. This proves the proposition.

Q.E.D.

We can now establish the non-archimedean extension of $\chi_{H}$.

17 - Lemma ($\chi_{H}:\mathbb{N}_{0}\rightarrow\mathbb{Q}$ extends to
$\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q_{H}}$ whenever $H$ is
semi-basic): Let $H$ be semi-basic. For brevity, write $q=q_{H}$. Then, the
limit555We write $\overset{\mathbb{Z}_{q}}{=}$ to emphasize that any notions
of convergence implicit in the expressions joined by
$\overset{\mathbb{Z}_{q}}{=}$ occur in $\mathbb{Z}_{q}$, and likewise for
$\overset{\mathbb{Z}_{\varrho}}{=}$ and convergence in
$\mathbb{Z}_{\varrho}$.:

$\chi_{H}\left(\mathfrak{z}\right)\overset{\mathbb{Z}_{q}}{=}\lim_{n\rightarrow\infty}\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{n}}\right)$
(43)

exists for all $\mathfrak{z}\in\mathbb{Z}_{\varrho}$, and thereby defines the
unique interpolation of $\chi_{H}$ to a function
$\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q}$, with $\chi_{H}$
being continuous on $\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$. Moreover:

I.

$\chi_{H}\left(\varrho\mathfrak{z}+j\right)\overset{\mathbb{Z}_{q}}{=}\frac{a_{j}\chi_{H}\left(\mathfrak{z}\right)+b_{j}}{d_{j}},\textrm{
}\forall\mathfrak{z}\in\mathbb{Z}_{\varrho}$ (44)

II. The interpolation $\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q}$
defined by the limit (43) is the unique function from $\mathbb{Z}_{\varrho}$
to $\mathbb{Z}_{q}$ satisfying (44).

_Remark_ : We use the term rising limit to denote the form of limit given in
43; that is, a rising limit of a function
$f:\mathbb{Z}_{\varrho}\rightarrow\mathcal{X}$ taking values in a metric space
$\mathcal{X}$ is the expression
$\lim_{n\rightarrow\infty}f\left(\left[\mathfrak{z}\right]_{\varrho^{n}}\right)$,
with the limit taking place in $\mathcal{X}$.

Proof: By (26) and (30), we have that:

$\chi_{H}\left(\mathbf{j}\right)=H_{\mathbf{j}}\left(0\right)=\sum_{m=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{m}}}{d_{j_{m}}}\prod_{k=1}^{m-1}\frac{a_{j_{k}}}{d_{j_{k}}},\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$

Thus, for any $\mathbf{j}\in\textrm{String}\left(\varrho\right)$, the rational
number $\chi_{H}\left(\mathbf{j}\right)$ is an element of $\mathbb{Z}_{q}$.
Now, fixing a $\varrho$-adic integer $\mathfrak{z}\in\mathbb{Z}_{\varrho}$,
let
$\mathbf{j}\left(\mathfrak{z}\right)=\left(j_{1}\left(\mathfrak{z}\right),j_{2}\left(\mathfrak{z}\right),\ldots\right)$
denote the unique element of
$\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{\mathbb{N}_{1}}$ so that:

$\mathfrak{z}\overset{\mathbb{Z}_{\varrho}}{=}\sum_{\ell=1}^{\infty}j_{\ell}\left(\mathfrak{z}\right)\varrho^{\ell-1}$

where, as indicated, the convergence of the infinite series is with respect to
the topology on $\mathbb{Z}_{\varrho}$.

Next, note that our $\varrho$-adic integer $\mathfrak{z}$ will be a _rational_
integer (an element of $\mathbb{N}_{0}$) if and only if there is an $m$ so
that
$\mathfrak{z}\overset{\mathbb{Z}_{\varrho}}{=}\left[\mathfrak{z}\right]_{\varrho^{\ell}}$
for all $\ell\geq m$. That is to say, $\mathfrak{z}$ represents an element of
$\mathbb{N}_{0}$ if and only if $j_{\ell}\left(\mathfrak{z}\right)=0$ for all
$\ell\geq m$. Consequently, for all $\ell\geq m$:

$\displaystyle\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{\ell}}\right)$
$\displaystyle=H_{\left(j_{1}\left(\mathfrak{z}\right),\ldots,j_{m}\left(\mathfrak{z}\right),j_{m+1}\left(\mathfrak{z}\right),\ldots,j_{\ell}\left(\mathfrak{z}\right)\right)}\left(0\right)$
$\displaystyle\left(j_{\ell}\left(\mathfrak{z}\right)=0,\textrm{
}\forall\ell\geq m\right);$
$\displaystyle=H_{\left(j_{1}\left(\mathfrak{z}\right),\ldots,j_{m}\left(\mathfrak{z}\right)\right)\wedge\underbrace{\left(0,\ldots,0\right)}_{\ell\textrm{
}0\textrm{s}}}\left(0\right)$
$\displaystyle=H_{\left(j_{1}\left(\mathfrak{z}\right),\ldots,j_{m}\left(\mathfrak{z}\right)\right)}\left(H_{0}^{\circ\ell}\left(0\right)\right)$
$\displaystyle\left(H_{0}\left(0\right)=0\right);$
$\displaystyle=H_{\left(j_{1}\left(\mathfrak{z}\right),\ldots,j_{m}\left(\mathfrak{z}\right)\right)}\left(0\right)$

and hence, given any integer $n\geq 0$, we have that
$\chi_{H}\left(\left[n\right]_{\varrho^{\ell}}\right)=\chi_{H}\left(n\right)$
for all sufficiently large $\ell$ (namely,
$\ell\geq\lambda_{\varrho}\left(n\right)$). This shows that (43) is satisfied
for $\mathfrak{z}\in\mathbb{Z}_{\varrho}\cap\mathbb{N}_{0}$.

Next, let $\mathfrak{z}$ be an element of $\mathbb{Z}_{\varrho}$ which is
_not_ in $\mathbb{N}_{0}$. Then, it must be that
$j_{\ell}\left(\mathfrak{z}\right)\neq 0$ for infinitely many $\ell$. Letting:

$\mathbf{j}_{m}\left(\mathfrak{z}\right)\overset{\textrm{def}}{=}\left(j_{1}\left(\mathfrak{z}\right),\ldots,j_{m}\left(\mathfrak{z}\right)\right)\sim\left[\mathfrak{z}\right]_{\varrho^{m}}$

denote the tuple containing the first $m$ entries of
$\mathbf{j}\left(\mathfrak{z}\right)$ (a tuple which then represents the
rational integer $\left[\mathfrak{z}\right]_{\varrho^{m}}$) we have that:

$\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{m}}\right)=\chi_{H}\left(\mathbf{j}_{m}\left(\mathfrak{z}\right)\right)=\sum_{\ell=1}^{m}\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}\prod_{k=1}^{\ell-1}\frac{a_{j_{k}\left(\mathfrak{z}\right)}}{d_{j_{k}\left(\mathfrak{z}\right)}}$
(45)

Now, note that:

$\prod_{k=1}^{\ell-1}\frac{a_{j_{k}\left(\mathfrak{z}\right)}}{d_{j_{k}\left(\mathfrak{z}\right)}}=M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right),\textrm{
}\forall\ell\in\mathbb{N}_{1}$ (46)

where we adopt the convention that
$\mathbf{j}_{0}\left(\mathfrak{z}\right)\overset{\textrm{def}}{=}0$. As such,
we can write (45) as:

$\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{m}}\right)=\sum_{\ell=1}^{m}\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)$
(47)

Since $j_{\ell}\left(\mathfrak{z}\right)\neq 0$ for infinitely many $\ell$,
the number of non-zero entries in $\mathbf{j}_{\ell}\left(\mathfrak{z}\right)$
tends monotonically to $\infty$ as $\ell\rightarrow\infty$. Thus, by 16, the
$q$-adic absolute value of
$M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)$ tends to $0$
as $\ell\rightarrow\infty$. Additionally, since $H$ is semi-basic, 15 tell us
that every $d_{j}$ is co-prime to $q$, and hence,
$\left|d_{j_{\ell}\left(\mathfrak{z}\right)}\right|_{q}=1$ for all $\ell$.
Thus, for all $\ell\leq 1$:

$\displaystyle\left|\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)\right|_{q}$
$\displaystyle=\left|b_{j_{\ell}\left(\mathfrak{z}\right)}\right|_{q}\cdot\left|M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)\right|_{q}$
$\displaystyle\left(b_{j_{\ell}\left(\mathfrak{z}\right)}\in\mathbb{Z}\Rightarrow\left|b_{j_{\ell}\left(\mathfrak{z}\right)}\right|_{q}\leq
1\right);$
$\displaystyle\leq\left|M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)\right|_{q}$
$\displaystyle\left(\textrm{{16}}\right);$ $\displaystyle\leq
q^{-\left(\textrm{number of non-zero entries of
}\mathbf{i}_{\ell}\left(\mathfrak{z}\right)\right)}$

and so, taking the limit of (47) in $\mathbb{Z}_{q}$ as $m\rightarrow\infty$,
we obtain the infinite series expression:

$\lim_{m\rightarrow\infty}\chi_{H}\left(\left[\mathfrak{z}\right]_{\varrho^{m}}\right)\overset{\mathbb{Z}_{q}}{=}\sum_{\ell=1}^{\infty}\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)$
(48)

where
$\left|\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)\right|_{q}\rightarrow
0$ as $\ell\rightarrow\infty$. It is a well-known property of the non-
archimedean metric induced by $\left|\cdot\right|_{q}$ (see [15]) that a
series $\sum_{n=0}^{\infty}\mathfrak{a}_{n}$ of $q$-adic numbers converges to
a limit in $\mathbb{Q}_{\varrho}$ _if and only if
$\left|\mathfrak{a}_{n}\right|_{q}\rightarrow 0$_ _._ Thus, (48) is convergent
for all $\mathfrak{z}\in\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$.
Moreover, since each term of the sum in (48) has $q$-adic magnitude $\leq 1$,
each term is a $q$-adic integer, and hence, the sum of the series is, itself,
a $q$-adic integer.

Now, let $\left\\{\mathfrak{z}_{n}\right\\}_{n\geq
1}\subseteq\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$ be a sequence
converging in $\mathbb{Z}_{\varrho}$ to an element
$\mathfrak{z}\in\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$. Since
$\mathfrak{z}$ and the $\mathfrak{z}_{n}$s are all $\varrho$-adic integers
which are not non-negative rational integers, $\mathfrak{z}$ and the
$\mathfrak{z}_{n}$s necessarily have infinitely many non-zero digits. Thus, we
have that:

$\lim_{\ell\rightarrow\infty}\sup_{n\geq
1}\left|\frac{b_{j_{\ell}\left(\mathfrak{z}_{n}\right)}}{d_{j_{\ell}\left(\mathfrak{z}_{n}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}_{n}\right)\right)\right|_{q}=0$
(49)

that is, the convergence of the series in (48) which defines
$\chi_{H}\left(\mathfrak{z}_{n}\right)$ occurs _uniformly_ with respect to
$n$. This justifies the interchange of limit and infinite sum in:

$\displaystyle\lim_{n\rightarrow\infty}\chi_{H}\left(\mathfrak{z}_{n}\right)$
$\displaystyle\overset{\mathbb{Z}_{q}}{=}\lim_{n\rightarrow\infty}\lim_{m\rightarrow\infty}\chi_{H}\left(\left[\mathfrak{z}_{n}\right]_{\varrho^{m}}\right)$
$\displaystyle\overset{\mathbb{Z}_{q}}{=}\lim_{n\rightarrow\infty}\sum_{\ell=1}^{\infty}\frac{b_{j_{\ell}\left(\mathfrak{z}_{n}\right)}}{d_{j_{\ell}\left(\mathfrak{z}_{n}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}_{n}\right)\right)$
$\displaystyle\left(\textrm{by }(\ref{eq:Uniform
convergence});\mathfrak{z}_{n}\rightarrow\mathfrak{z}\textrm{ in}\textrm{
}\mathbb{Z}_{\varrho}\right);$
$\displaystyle\overset{\mathbb{Z}_{q}}{=}\sum_{\ell=1}^{\infty}\frac{b_{j_{\ell}\left(\mathfrak{z}\right)}}{d_{j_{\ell}\left(\mathfrak{z}\right)}}M_{H}\left(\mathbf{j}_{\ell-1}\left(\mathfrak{z}\right)\right)$
$\displaystyle\left(\textrm{by }(\ref{eq:Formal rising limit of
Chi_H})\right);$
$\displaystyle\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(\mathfrak{z}\right)$

Thus, by the sequential definition of continuity, we have that $\chi_{H}$ is
continuous on $\mathbb{Z}_{\varrho}\backslash\mathbb{N}_{0}$.

Finally, one can prove (I) by the same argument used to prove (34). The
argument used to prove that $\chi_{H}$ is the unique function on
$\mathbb{N}_{0}$ satisfying (34) can then be used to prove (II)—that is, to
prove that the interpolation
$\chi_{H}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q}$ is the unique
$q$-adic valued function on $\mathbb{Z}_{\varrho}$ satisfying (44).

Q.E.D.

We can now prove Theorem I from the Introduction:

18 - Proof of Theorem I: Combine the Lemmas 12 and 17.

Q.E.D.

Our goal—the Correspondence Theorem (a.k.a Theorem II)—relates the periodic
points of $H$ in $\mathbb{Z}$ to the set
$\mathbb{Z}\cap\chi_{H}\left(\mathbb{Z}_{\varrho}\right)$, where we view both
$\mathbb{Z}$ and $\chi_{H}\left(\mathbb{Z}_{\varrho}\right)$ as being embedded
in $\mathbb{Z}_{q}$. The distinction between basic-ness and semi-basic-ness
plays a key role here, as there is an additional property (“proper”-ness to be
defined below), satisfied when $H$ is basic, a property needed to ensure that
the set $\mathbb{Z}\cap\chi_{H}\left(\mathbb{Z}_{\varrho}\right)$ fully
characterizes the periodic points of $H$. There may be conditions under which
the basicness of $H$ could be relaxed to semi-basicness without affecting the
conclusion of the Correspondence Theorem, however, we shall not pursue this
question here.

Before proceeding, we will also need a certain self-map of
$\mathbb{Z}_{\varrho}$—which we denote $B_{\varrho}$—in order to formulate the
functional equation satisfied by $\chi_{H}$. First, however, a useful
observation which will motivate the definition of $B_{\varrho}$.

19 - Proposition: Let $\varrho$ be an integer $\geq 2$, let
$n\in\mathbb{N}_{1}$, and let
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ be the shortest string
representing $n$. Then, for all $m\in\mathbb{N}_{1}$:

$\mathbf{j}^{\wedge m}\sim
n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}$
(50)

That is to say, the quantity on the right is the integer whose $\varrho$-adic
expansion consists of $m$ concatenated copies of the $\varrho$-adic expansion
of $n$.

Proof: A straightforward computation.

Q.E.D.

20 - Definition: Let $\varrho$ be an integer $\geq 2$. Then, we define
$B_{\varrho}:\mathbb{N}_{0}\rightarrow\mathbb{Q}\cap\mathbb{Z}_{\varrho}$ by:

$B_{\varrho}\left(n\right)\overset{\textrm{def}}{=}\begin{cases}0&\textrm{if
}n=0\\\ \frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}&\textrm{if
}n\geq 1\end{cases}$ (51)

_Remark_ : Note that $B$ extends to a function on $\mathbb{Z}_{\varrho}$, one
whose restriction to $\mathbb{Z}_{\varrho}/\mathbb{N}_{0}$ is identity map.

Now we establish the functional equation for $\chi_{H}$ implicit in cycle-
generating formulas like (8) and (16).

21 - Lemma ($\chi_{H}\circ B_{\varrho}$’s Functional Equation): Let $H$ be
semi-basic. Then:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)},\textrm{
}\forall n\in\mathbb{N}_{1}$ (52)

Proof: Let $n\in\mathbb{N}_{1}$, and let
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ be the shortest string
representing $n$. Now, for all $m\geq 1$ and all $k\in\mathbb{N}_{1}$:

$H_{\mathbf{j}^{\wedge m}}\left(k\right)=H_{\mathbf{j}}^{\circ
m}\left(k\right)$

Since:

$H_{\mathbf{j}}\left(k\right)=M_{H}\left(\mathbf{j}\right)k+\chi_{H}\left(\mathbf{j}\right)$

the geometric series formula yields:

$H_{\mathbf{j}^{\wedge m}}\left(k\right)=H_{\mathbf{j}}^{\circ
m}\left(k\right)=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}k+\frac{1-\left(M_{H}\left(\mathbf{j}\right)\right)^{m}}{1-M_{H}\left(\mathbf{j}\right)}\chi_{H}\left(\mathbf{j}\right)$

Since we also have:

$H_{\mathbf{j}^{\wedge m}}\left(k\right)=M_{H}\left(\mathbf{j}^{\wedge
m}\right)k+\chi_{H}\left(\mathbf{j}^{\wedge m}\right)$

this then yields:

$M_{H}\left(\mathbf{j}^{\wedge m}\right)k+\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}k+\frac{1-\left(M_{H}\left(\mathbf{j}\right)\right)^{m}}{1-M_{H}\left(\mathbf{j}\right)}\chi_{H}\left(\mathbf{j}\right)$

By (40), we see that $M_{H}\left(\mathbf{j}^{\wedge
m}\right)k=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}k$, and hence:

$\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\frac{1-\left(M_{H}\left(\mathbf{j}\right)\right)^{m}}{1-M_{H}\left(\mathbf{j}\right)}\chi_{H}\left(\mathbf{j}\right)$
(53)

Now, by (50), we have that:

$\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\chi_{H}\left(n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)$

where the equality is of rational numbers in $\mathbb{R}$. Since
$n\in\mathbb{N}_{1}$, the sequence
$\left\\{n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right\\}_{m\geq
1}$ is a convergent rising-limit in $\mathbb{Z}_{\varrho}$. Hence, taking the
rising limit of $\chi_{H}$ in terms of $\mathbf{j}$ ($\mathbf{j}^{\wedge m}$
as $m\rightarrow\infty$, rather than $\left[\mathfrak{z}\right]_{\varrho^{m}}$
as $m\rightarrow\infty$, where $\mathfrak{z}\sim\mathbf{j}^{\wedge\infty}$)
allows us to conclude that:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(\frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)\overset{\mathbb{Z}_{q}}{=}\lim_{m\rightarrow\infty}\chi_{H}\left(n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)\overset{\mathbb{Z}_{q}}{=}\lim_{m\rightarrow\infty}\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)$

Additionally, because $H$ is semi-basic, it then follows by 16 that
$\left|M_{H}\left(\mathbf{j}\right)\right|_{q}<1$ (since $\mathbf{j}$ has a
non-zero entry), and hence, that
$\left(M_{H}\left(\mathbf{j}\right)\right)^{m}$ tends to $0$ in
$\mathbb{Z}_{q}$ as $m\rightarrow\infty$. Thus, letting $m\rightarrow\infty$,
the equality (53) passes to an equality in $\mathbb{Z}_{q}$:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}\lim_{m\rightarrow\infty}\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)\overset{\mathbb{Z}_{q}}{=}\lim_{m\rightarrow\infty}\left(\frac{1-\left(M_{H}\left(\mathbf{j}\right)\right)^{m}}{1-M_{H}\left(\mathbf{j}\right)}\chi_{H}\left(\mathbf{j}\right)\right)\overset{\mathbb{Z}_{q}}{=}\frac{\chi_{H}\left(\mathbf{j}\right)}{1-M_{H}\left(\mathbf{j}\right)}$

Replacing $\mathbf{j}$ on the far right with $n$ then yields (52), as desired.

Q.E.D.

_Remark_ : As seen in the above proof, (52) is really just the geometric
series summation formula, convergent in $\mathbb{Z}_{q}$ whenever
$\left|M_{H}\left(n\right)\right|_{q}<1$. In computing
$\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ by using (48) with
$\mathfrak{z}=B_{\varrho}\left(n\right)$ and $n\geq 1$, the series in (48)
will reduce to a geometric series, one which converges in $\mathbb{Z}_{q}$ to
$\chi_{H}\left(n\right)/\left(1-M_{H}\left(n\right)\right)$. Additionally, for
any $n\geq 1$ for which the _archimedean_ absolute value
$\left|M_{H}\left(n\right)\right|$ is less than $1$, the _universality_ of the
geometric series formula:

$\sum_{n=0}^{\infty}x^{n}=\frac{1}{1-x}$

guarantees that the limit to which the series in (48) converges to in
$\mathbb{R}$ in this case is the same as the limit to which it converges in
$\mathbb{Z}_{q}$ [4]. This is worth mentioning because, as we shall see, the
values of $n\geq 1$ for which
$\chi_{H}\left(n\right)/\left(1-M_{H}\left(n\right)\right)$ is a periodic
point of $H$ in $\mathbb{N}_{1}$ (the integers $\geq 1$) are exactly those
values of $n\geq 1$ for which the non-archimedean absolute value
$\left|M_{H}\left(n\right)\right|$ is $<1$.

Now we introduce the final bit of qualitative controls for $H$’s behavior that
we will need to prove the Correspondence Theorem (Theorem II).

22 - Definition:

I. We say a real number $x$ is a wrong value for $H$ whenever there is a
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ so that:

$x=H_{\mathbf{j}}\left(n\right)=\left(H_{j_{1}}\circ\cdots\circ
H_{j_{\left|\mathbf{j}\right|}}\right)\left(n\right)$

for some $n\in\mathbb{Z}$ with
$n\overset{\varrho}{\cancel{\equiv}}j_{\left|\mathbf{j}\right|}$. We call $n$
the seed of $x$.

_Remarks_ :

i. That is to say, a wrong value $x$ is the image of an integer $n$ under some
composition sequence of the $H_{j}$s so that the first branch ($H_{j_{m}}$)
applied to $n$ is not the “correct” choice of branch (that is,
$H_{j_{m}}\left(n\right)\neq H\left(n\right)$).

ii. If $x$ is a wrong value of $H$ with seed $n$ so that
$x=H_{\mathbf{j}}\left(n\right)$ for some string $\mathbf{j}$, note that for
any $\mathbf{i}\in\textrm{String}\left(\varrho\right)$,
$H_{\mathbf{i}}\left(x\right)=H_{\mathbf{i}}\left(H_{\mathbf{j}}\left(n\right)\right)=H_{\mathbf{i}\wedge\mathbf{j}}\left(n\right)$
will _also_ be a wrong value of $H$ with seed $n$. Thus, branches of $H$ will
always map wrong values to wrong values.

II. We say $H$ is proper whenever _every_ wrong value of $H$ is a _non-
integer_ rational number.

_Remark_ : Being proper means that once we apply the “wrong” choice of branch
to an integer $n$ to obtain the wrong value $x$, $x$ will be a non-integer,
and, furthermore, $H_{\mathbf{j}}\left(x\right)$ will remain a non-integer for
all $\mathbf{j}$. In other words, when $H$ is proper, once you make a “wrong
choice”, you move off $\mathbb{Z}$, and, can never return to $\mathbb{Z}$ by
applying branches of $H$.

23 - Lemma: If $H$ is basic, then $H$ is proper.

Proof: Let $H$ be basic. By way of contradiction, suppose there is a wrong
value $x=H_{\mathbf{j}}\left(n\right)$ which is an integer. Consequently,
$\left[n\right]_{\varrho}$—the value of $n$ mod $\varrho$—is not equal to
$j_{L}$, the last entry of $\mathbf{j}$. Now, using the formulae (29) and
(30), for any $\mathbf{j}\in\textrm{String}\left(\varrho\right)$ and any
$n\in\mathbb{Z}$, we can write:

$x=H_{\mathbf{j}}\left(n\right)=M_{H}\left(\mathbf{j}\right)n+\chi_{H}\left(\mathbf{j}\right)=\left(\prod_{k=1}^{L}\mu_{j_{k}}\right)n\varrho^{-L}+\sum_{m=1}^{L}\frac{b_{j_{m}}}{a_{j_{m}}}\left(\prod_{k=1}^{m}\mu_{j_{k}}\right)\varrho^{-m}$

where, for aesthetic’s sake, we write $L$ instead of
$\left|\mathbf{j}\right|$. Since $H$ is basic, $\mu_{j}=a_{j}$ for all $j$;
using this and multiplying through on both sides of the above by
$\varrho^{L}$, we obtain:

$\varrho^{L}x=\left(\prod_{k=1}^{L}a_{j_{k}}\right)n+\sum_{m=1}^{L}b_{j_{m}}\left(\prod_{k=1}^{m-1}a_{j_{k}}\right)\varrho^{L-m}$
(54)

where the $k$-product is defined to be $1$ when $m=1$. Since $H$ is basic,
$d_{j}=\varrho$ for all $j$; as such, the co-primality condition on
$H$—$\gcd\left(a_{j},d_{j}\right)=1$ for all $j$—((condition (I) below (1))
required of $H$ ensures that every $a_{j}$ is co-prime to $\varrho$, and thus,
that $\left|a_{j}\right|_{\varrho}=1$ for all $j$.

Next, we re-write (54) like so, pulling out the $m=L$ term:

$\varrho^{L}x=\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)\underbrace{\left(a_{j_{L}}n+b_{j_{L}}\right)}_{\varrho
H_{j_{L}}\left(n\right)}+\sum_{m=1}^{L-1}b_{j_{m}}\left(\prod_{k=1}^{m-1}a_{j_{k}}\right)\varrho^{L-m}$

Dividing by $\varrho$ gives:

$\underbrace{\varrho^{L-1}x}_{\in\mathbb{Z}}=\underbrace{\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)}_{\in\mathbb{Z}}H_{j_{L}}\left(n\right)+\underbrace{\sum_{m=1}^{L-1}b_{j_{m}}\left(\prod_{k=1}^{m-1}a_{j_{k}}\right)\varrho^{L-1-m}}_{\in\mathbb{Z}}$

Writing $n=\varrho\nu+\ell$, where $\nu\in\mathbb{Z}$ and
$\ell=\left[n\right]_{\varrho}\neq j_{L}$, we have that (since
$d_{j_{L}}=\varrho$):

$H_{j_{L}}\left(n\right)=\frac{a_{j_{L}}\left(\varrho\nu+\ell\right)+b_{j_{L}}}{\varrho}=a_{j_{L}}\nu+\frac{a_{j_{L}}\ell+b_{j_{L}}}{\varrho}=a_{j_{L}}\nu+H_{j_{L}}\left(\ell\right)$

Thus, our equation becomes:

$\underbrace{\varrho^{L-1}x}_{\in\mathbb{Z}}=\underbrace{\left(\prod_{k=1}^{L}a_{j_{k}}\right)\nu}_{\in\mathbb{Z}}+\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)H_{j_{L}}\left(\ell\right)+\underbrace{\sum_{m=1}^{L-1}b_{j_{m}}\left(\prod_{k=1}^{m-1}a_{j_{k}}\right)\varrho^{L-1-m}}_{\in\mathbb{Z}}$
(55)

Since $\ell\neq j_{L}$, by the integrality property of $H$ (condition (II)
below (1)), we have that
$H_{j_{L}}\left(\ell\right)=\frac{a_{j_{L}}\ell+b_{j_{L}}}{\varrho}$ is not an
integer; that is, the integer $a_{j_{L}}\ell+b_{j_{L}}$ is not a multiple of
$\varrho$. Since the basicness of $H$ guarantees that $a_{j}$ is co-prime to
$\varrho$ for all $j$, it follows that the quantity:

$\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)H_{j_{L}}\left(\ell\right)=\frac{\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)\left(a_{j_{L}}\ell+b_{j_{L}}\right)}{\varrho}$

is a non-integer, because the numerator on the right is not a multiple of
$\varrho$. However, (55) shows that
$\left(\prod_{k=1}^{L-1}a_{j_{k}}\right)H_{j_{L}}\left(\ell\right)$ can be
written as the sum and difference of three integers, and is therefore an
integer. This is a contradiction! Thus, it must be that $x$ is a non-integer.

This shows that if $H$ is basic, every wrong value of $H$ must be an
integer—that is, that $H$ is proper.

Q.E.D.

Next, we need an essentially trivial observation: if
$H_{\mathbf{j}}\left(n\right)=n$, $H\left(0\right)=0$, and
$\left|\mathbf{j}\right|\geq 2$, then $\mathbf{j}$ must contain at least one
non-zero entry.

24 - Proposition: Let $H\left(0\right)=0$ and suppose $H$ is non-degenerate
(that is, assume $a_{j}\neq 1$ for all non-zero $j$). Let $n\in\mathbb{Z}$ be
a periodic point of $H$, and let $\Omega$ be the cycle of $H$ which contains
$n$. Then, letting
$\mathbf{j}=\left(j_{1},\ldots,j_{\left|\Omega\right|}\right)\in\left(\mathbb{Z}/\varrho\mathbb{Z}\right)^{\left|\Omega\right|}$
be the unique string so that:

$H_{\mathbf{j}}\left(n\right)=H^{\circ\left|\Omega\right|}\left(n\right)=n$

we have that either $\left|\Omega\right|=1$ (i.e., $n$ is a fixed point of
$H$), or, there is an $\ell\in\left\\{1,\ldots,\left|\Omega\right|\right\\}$
so that $j_{\ell}\neq 0$.

Proof: Let $H$, $n$, and $\mathbf{j}$ be as given, and suppose
$\left|\Omega\right|\geq 2$. Since $H$ is non-degenerate, $a_{j}\neq 1$ for
any $j\in\left\\{1,\ldots,\varrho-1\right\\}$. Then, by way of contradiction,
suppose that $j_{\ell}=0$ for every $\ell$. Then, since $\mathbf{j}$ contains
only $0$s:

$n=H_{\mathbf{j}}\left(n\right)=H_{0}^{\circ\left|\Omega\right|}\left(n\right)$

Since $H_{0}$ is an affine linear map of the form
$H_{0}\left(x\right)=\frac{a_{0}x+b_{0}}{d_{0}}$, and since $b_{0}=0$, this
map has exactly one fixed point: $0$, Moreover, $0$ is also the only fixed
point of $H_{0}^{\circ m}\left(x\right)$, for all $m\geq 1$. Thus,
$n=H_{0}^{\circ\left|\Omega\right|}\left(n\right)$ forces $n=0$, and hence,
force $H\left(n\right)=H_{0}\left(n\right)=n$. Thus, the cycle $\Omega$ to
which $n$ belongs contains only one element: $n$ itself. This contradicts the
assumption that $\left|\Omega\right|\geq 2$.

Q.E.D.

Now we can prove the Correspondence Theorem as stated in the Introduction. The
version given here is slightly more specific than the version stated in the
introduction, seeing as we utilize $B_{\varrho}$ in its formulation.

25 - Theorem (Correspondence Theorem, Ver. 1): Let $H$ be basic, and let
$q=q_{H}$ be as defined in (4). Then:

I. Let $\Omega$ be any cycle of $H$ in $\mathbb{Z}$, with
$\left|\Omega\right|\geq 2$. Then, there exist $x\in\Omega$ and
$n\in\mathbb{N}_{1}$ so that:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}x$

That is, there is an $n$ so that the infinite series defining
$\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ converges in $\mathbb{Z}_{q}$
to $x$.

II. Let $n\in\mathbb{N}_{1}$. If:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)\in\mathbb{Z}_{q}\cap\mathbb{Z}$

(that is, if the $\mathbb{Z}_{q}$-convergent series defining
$\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ converges to a _rational_
integer), then $\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ is a periodic
point of $H$ in $\mathbb{Z}$.

_Remarks_ :

i. For the case of the $T_{a}$ maps (where $a$ is an odd integer $\geq 3$), it
can be shown that the set of _odd_ periodic points of $T_{a}$ in $\mathbb{Z}$
is equal to
$\chi_{H}\left(B_{\varrho}\left(\mathbb{N}_{1}\right)\right)\cap\mathbb{Z}$.

ii. If $H$ is merely semi-basic, (I) holds, but (II) need not hold, meaning
that not every rational integer value attained by $\chi_{H}$ over
$\mathbb{Z}_{\varrho}$ need be a periodic point of $H$.

Proof:

I. Let $\Omega$ be a cycle of $H$ in $\mathbb{Z}$, with
$\left|\Omega\right|\geq 2$. Since $\left|\Omega\right|\geq 2$, 24 guarantees
that for any $x\in\Omega$ and any
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ for which
$\left|\mathbf{j}\right|=\left|\Omega\right|\geq 2$ and
$H_{\mathbf{j}}\left(\omega\right)=x$, it must be that $\mathbf{j}$ contains
at least one non-zero entry. Additionally, note that for any
$x^{\prime}\in\Omega\backslash\left\\{x\right\\}$, the unique string
$\mathbf{i}$ of length $\left|\Omega\right|$ so that
$H_{\mathbf{i}}\left(x^{\prime}\right)=x^{\prime}$ will be a cyclic
permutation of the entries of $\mathbf{j}$. In particular, there is a
bijective correspondence between $\Omega$ and the set of all
length-$\left|\Omega\right|$ strings obtained by cyclically permuting the
entries of $\mathbf{j}$. As such, without loss of generality, we can assume
that $x$ was chosen so that the known non-zero entry of $\mathbf{j}$ occurs in
the right-most entry of $\mathbf{j}$ (that is,
$j_{\left|\mathbf{j}\right|}\neq 0$).

Now, writing the affine map $H_{\mathbf{j}}$ in affine form, we have that:

$x=H_{\mathbf{j}}\left(\omega\right)=H_{\mathbf{j}}^{\prime}\left(0\right)x+H_{\mathbf{j}}\left(0\right)=M_{H}\left(\mathbf{j}\right)x+\chi_{H}\left(\mathbf{j}\right)$

where all the equalities are in $\mathbb{R}$. Moreover, since
$H_{\mathbf{j}}\left(x\right)=x$ implies $H_{\mathbf{j}^{\wedge
m}}\left(x\right)=x$, we then have:

$x=H_{\mathbf{j}^{\wedge m}}\left(x\right)=M_{H}\left(\mathbf{j}^{\wedge
m}\right)x+\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}x+\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)$

Since $\mathbf{j}$ contains a non-zero666If $\mathbf{j}$ had a zero in its
right-most entry, $\lambda_{\varrho}\left(n\right)$ would be strictly _less_
than $\left|\mathbf{j}\right|$, because $n$ could be represented by a string
shorter than $\mathbf{j}$—simply remove the right-most zero entry from
$\mathbf{j}$. entry, we have that
$\left|\left(M_{H}\left(\mathbf{j}\right)\right)^{m}\right|_{q}\rightarrow 0$
as $m\rightarrow\infty$, and that $\mathbf{j}\sim n$ for some positive integer
$n$ with $\lambda_{\varrho}\left(n\right)=\left|\mathbf{j}\right|$. By 19, we
have that:

$\mathbf{j}\sim
n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}$

and hence, like in the proof of 21:

$\lim_{m\rightarrow\infty}\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\lim_{m\rightarrow\infty}\chi_{H}\left(n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(\frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)=\chi_{H}\left(B_{\varrho}\left(n\right)\right)$

Thus, in:

$x=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}x+\chi_{H}\left(\mathbf{j}^{\wedge
m}\right)=\left(M_{H}\left(\mathbf{j}\right)\right)^{m}x+\chi_{H}\left(n\frac{1-\varrho^{m\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)$

letting $m\rightarrow\infty$ gives the equality:

$x\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(\frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)=\chi_{H}\left(B_{\varrho}\left(n\right)\right)$

over $\mathbb{Z}_{q}$, which proves the existence of the desired $x$ and $n$.
$\checkmark$

II. Let $n$ be an integer $\geq 1$, and let
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ be the shortest string
representing $n$. Then, by (38):

$\chi_{H}\left(n\frac{1-\varrho^{k\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)=\chi_{H}\left(\mathbf{j}^{\wedge
k}\right)=H\left(\chi_{H}\left(\mathbf{j}^{\wedge\left(k-1\right)}\right)\right)=\cdots=H^{\circ\left(k-1\right)}\left(\chi_{H}\left(\mathbf{j}\right)\right)$
(56)

Letting $k\rightarrow\infty$, the rising-continuity of $\chi_{H}$ over
$\mathbb{Z}_{\varrho}$ and the convergence of
$n\frac{1-\varrho^{k\lambda_{\varrho}\left(n\right)}}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}$
to
$\frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}=B_{\varrho}\left(n\right)$
in $\mathbb{Z}_{\varrho}$ then yields the $q$-adic equality:

$\lim_{k\rightarrow\infty}H_{\mathbf{j}}^{\circ\left(k-1\right)}\left(\chi_{H}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(\frac{n}{1-\varrho^{\lambda_{\varrho}\left(n\right)}}\right)=\chi_{H}\left(B_{\varrho}\left(n\right)\right)$
(57)

Sine $H$ is basic, we have that $\gcd\left(a_{j},\varrho\right)=1$ for all
$j$, and hence, that for any finite length string such as our $\mathbf{j}$,
the quantities $H_{\mathbf{j}}^{\prime}\left(0\right)$ and
$H_{\mathbf{j}}\left(0\right)$ are rational numbers that lie in
$\mathbb{Z}_{q}$. As such, the affine linear map
$H_{\mathbf{j}}\left(\mathfrak{z}\right)=H_{\mathbf{j}}^{\prime}\left(0\right)\mathfrak{z}+H_{\mathbf{j}}\left(0\right)$
defines a continuous self-map of $\mathbb{Z}_{q}$, which allows us to write:

$H_{\mathbf{j}}\left(\chi_{H}\left(B_{\varrho}\left(n\right)\right)\right)\overset{\mathbb{Z}_{q}}{=}H_{\mathbf{j}}\left(\lim_{k\rightarrow\infty}H_{\mathbf{j}}^{\circ\left(k-1\right)}\left(\chi_{H}\left(n\right)\right)\right)\overset{\mathbb{Z}_{q}}{=}\lim_{k\rightarrow\infty}H_{\mathbf{j}}^{\circ
k}\left(\chi_{H}\left(n\right)\right)\overset{\mathbb{Z}_{q}}{=}\chi_{H}\left(B_{\varrho}\left(n\right)\right)$

and hence, $\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ is then a fixed
point of the composition sequence $H_{\mathbf{j}}$. Additionally, by (52), we
know that:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$

Now, let us assume the hypotheses of (II); namely, that
$\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\in\mathbb{Z}_{q}\cap\mathbb{Z}$.

Claim:

$H_{\mathbf{j}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)=H^{\circ\left|\mathbf{j}\right|}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$
(58)

That is to say, in applying each of the branches specified by $\mathbf{j}$ to
the integer $\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$, at no
point in the process was the “wrong” branch applied.

Proof of Claim: Recall that our $\mathbf{j}$ was chosen to be the shortest
string representing $n$. To that end, for each
$m\in\left\\{1,\ldots,\left|\mathbf{j}\right|\right\\}$, let us write
$\mathbf{j}_{m}=\left(j_{1},\ldots,j_{m}\right)$ to denote the element of
$\textrm{String}\left(\varrho\right)$ whose entries are the first $m$ entries
of $\mathbf{j}$. Now, by way of contradiction, suppose $\mathbf{j}$ contains a
“wrong” branch; that is, suppose there is an $m$ so that:

$H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)\neq
H^{\circ m}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$

In other words, we are assuming that at some point in the applying the first
$m$ branches of $H$ specified by $\mathbf{j}$ to
$\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$, one of those branches
was “wrong”—that is, there must be a $k\in\left\\{1,\ldots,m\right\\}$ so that
$j_{k}\neq\left[H_{\mathbf{j}_{k-1}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)\right]_{\varrho}$,
where $H_{\mathbf{j}_{0}}$ is defined to be the identity map. Then,
$H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$
would be a wrong value of $H$.

Since $H$ was given to be basic, by 23, $H$ is proper. Thus, the wrong value
is
$H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$
not an integer. Moreover,
$H_{\mathbf{i}}\left(H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)\right)$
is a non-integer for all $\mathbf{i}\in\textrm{String}\left(\varrho\right)$.
Letting $\mathbf{i}=\left(j_{m+1},\ldots,j_{\left|\mathbf{j}\right|}\right)$,
we have that:

$H_{\mathbf{i}}\left(H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)\right)=H_{\mathbf{i}\wedge\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)=H_{\mathbf{j}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$

Since
$H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$
was a wrong value, so is
$H_{\mathbf{j}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$.
Moreover, since $H$ is proper,
$H_{\mathbf{j}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$
is not an integer. However, we assumed $n$ was such that
$\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$ was an integer. This is
a contradiction!

Thus, it must be that
$H_{\mathbf{j}_{m}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)=H^{\circ
m}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$ for all
$m\in\left\\{1,\ldots,\left|\mathbf{j}\right|\right\\}$. Hence,
$H_{\mathbf{j}}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)=H^{\circ\left|\mathbf{j}\right|}\left(\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}\right)$,
as claimed. $\checkmark$

In conclusion, we have that when $n\in\mathbb{N}_{1}$ (represented by
$\mathbf{j}$) makes $x=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$
into a rational integer, said rational integer satisfies:

$H^{\circ\left|\mathbf{j}\right|}\left(x\right)=\chi_{H}\left(x\right)$

where $\left|\mathbf{j}\right|=\lambda_{\varrho}\left(n\right)\geq 1$. Hence,
$x=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$ is then a periodic
point of $H$ in $\mathbb{Z}$, as desired. This proves (II). $\checkmark$

Q.E.D.

Using the functional equation (52), we can restate the Correspondence Theorem
in terms of $\chi_{H}$ and $M_{H}$.

26 - Corollary (Correspondence Theorem, Ver. 2): Let $H$ be basic. Then:

I. For every cycle $\Omega\subseteq\mathbb{Z}$ of $H$, viewing
$\Omega\subseteq\mathbb{Z}$ as a subset of $\mathbb{Z}_{q}$, the intersection
$\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\Omega$ is non-empty. Moreover,
for every $x\in\chi_{H}\left(\mathbb{Z}_{\varrho}\right)\cap\Omega$, there is
an $n\in\mathbb{N}_{1}$ so that:

$x=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$

where the equality occurs in $\mathbb{R}$.

II. Let $n\in\mathbb{N}_{1}$. If the quantity $x$ given by:

$x=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}$

is an integer, then $x$ is necessarily a periodic point of $H$. Moreover, $x$
is positive if and only if $M_{H}\left(n\right)<1$, and is negative if and
only if $M_{H}\left(n\right)>1$.

Proof: Re-write the results of 25 using (52). The positivity/negativity of $x$
stipulated in (II) follows by noting that $\chi_{H}\left(n\right)$ and
$M_{H}\left(n\right)$ are positive rational numbers for all
$n\in\mathbb{N}_{1}$.

Q.E.D.

Lastly, we have a version of the Correspondence Theorem which explicitly gives
the cycle-generating formula (16) in terms of $\mathbf{j}$, $\varrho$, the
$a_{j}$s, and the $b_{j}$s.

27 - Correspondence Theorem (Version 3): Let $H$ be basic. Then:

I. Let $\Omega$ be a cycle of $H$ containing at least two elements. Then,
there is an $x\in\Omega$, and a
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ of length $\geq 2$ so that:

$x=\frac{\sum_{n=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{n}}}{a_{j_{n}}}\left(\prod_{k=1}^{n}a_{j_{k}}\right)\varrho^{\left|\mathbf{j}\right|-n}}{\varrho^{\left|\mathbf{j}\right|}-\prod_{k=1}^{\left|\mathbf{j}\right|}a_{j_{k}}}$
(59)

II. Let $x\left(\mathbf{j}\right)=x\left(j_{1},\ldots,j_{N}\right)$ denote the
quantity:

$x\left(\mathbf{j}\right)\overset{\textrm{def}}{=}\frac{\sum_{n=1}^{\left|\mathbf{j}\right|}\frac{b_{j_{n}}}{a_{j_{n}}}\left(\prod_{k=1}^{n}a_{j_{k}}\right)\varrho^{\left|\mathbf{j}\right|-n}}{\varrho^{\left|\mathbf{j}\right|}-\prod_{k=1}^{\left|\mathbf{j}\right|}a_{j_{k}}},\textrm{
}\forall\mathbf{j}\in\textrm{String}\left(\varrho\right)$ (60)

Then, $x\left(\mathbf{j}\right)$ is a periodic point of $H$ for any
$\mathbf{j}\in\textrm{String}\left(\varrho\right)$ of length $\geq 2$ which
makes $x\left(\mathbf{j}\right)$ into a rational integer.

Proof: Use (29) and (30) on (I) and (II) of 26.

Q.E.D.

Finally, we prove Theorem II:

28 - Proof of Theorem II: Simply re-write the statement of 25.

Q.E.D.

## Conclusion

##  3 Baker, Catalan, and Collatz

The so-called Weak Collatz Conjecture is the assertion the only periodic
points of the Collatz map $C$ in the positive integers are $1$, $2$, and $4$.
Any proof of this conjecture will necessarily entail a significant advancement
in our understanding of transcendental number theory. In particular, it would
imply a proof of Baker’s Theorem much simpler than any currently known
method[18]. Baker’s Theorem concerns lower bounds on linear forms of
logarithms, expressions of the form:

$\left|\beta_{1}\ln\alpha_{1}+\cdots+\beta_{N}\ln\alpha_{N}\right|$ (61)

where the $\beta_{n}$s and $\alpha_{n}$s are complex algebraic numbers (with
all of the $\alpha_{n}$s being non-zero). Most proofs of Baker’s Theorem
employ a variant of what is known as Baker’s Method, in which one constructs
of an analytic function (called an auxiliary function) with a large number of
zeroes of specified degree so as to obtain contradictions on the assumption
that (61) is small. The import of Baker’s Theorem is that it allows one to
obtain lower bounds on expressions such as $\left|2^{m}-3^{n}\right|$, where
$m$ and $n$ are positive integers, and it was for applications such as these
in conjunction with the study of Diophantine equations that Baker earned the
Fields Medal. See [1] for a comprehensive account of the subject; also, parts
of [3].

With $\chi_{H}$ and the Correspondence Theorem at our disposal, we can get a
glimpse at the kinds of advancements in transcendental number theory that
might be needed in order to resolve the Weak Collatz Conjecture. To begin, it
is instructive to consider the following table of values for the various
functions utilized in this paper in the case of the $ax+1$ maps $T_{a}$ (3),
where $a$ is an odd integer $\geq 3$. For brevity, we write $\chi_{a}$ to
denote $\chi_{T_{a}}:\mathbb{Z}_{2}\rightarrow\mathbb{Z}_{a}$.

$n$ | $\\#_{2:1}\left(n\right)$ | $\lambda_{2}\left(n\right)$ | $\chi_{a}\left(n\right)$ | $\chi_{a}\left(B_{2}\left(n\right)\right)$ | $\chi_{3}\left(B_{2}\left(n\right)\right)$ | $\chi_{5}\left(B_{2}\left(n\right)\right)$
---|---|---|---|---|---|---
$0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$1$ | $1$ | $1$ | $\frac{1}{2}$ | $\frac{1}{2-a}$ | $-1$ | $-\frac{1}{3}$
$2$ | $1$ | $2$ | $\frac{1}{4}$ | $\frac{1}{4-a}$ | $1$ | $-1$
$3$ | $2$ | $2$ | $\frac{2+a}{4}$ | $\frac{2+a}{4-a^{2}}$ | $-1$ | $-\frac{1}{3}$
$4$ | $1$ | $3$ | $\frac{1}{8}$ | $\frac{1}{8-a}$ | $\frac{1}{5}$ | $\frac{1}{3}$
$5$ | $2$ | $3$ | $\frac{4+a}{8}$ | $\frac{4+a}{8-a^{2}}$ | $-7$ | $-\frac{9}{17}$
$6$ | $2$ | $3$ | $\frac{2+a}{8}$ | $\frac{2+a}{8-a^{2}}$ | $-5$ | $-\frac{7}{17}$
$7$ | $3$ | $3$ | $\frac{4+2a+a^{2}}{8}$ | $\frac{4+2a+a^{2}}{8-a^{3}}$ | $-1$ | $-\frac{1}{3}$
$8$ | $1$ | $4$ | $\frac{1}{16}$ | $\frac{1}{16-a}$ | $\frac{1}{13}$ | $\frac{1}{11}$
$9$ | $2$ | $4$ | $\frac{8+a}{16}$ | $\frac{8+a}{16-a^{2}}$ | $\frac{11}{7}$ | $-\frac{13}{9}$
$10$ | $2$ | $4$ | $\frac{4+a}{16}$ | $\frac{4+a}{16-a^{2}}$ | $1$ | $-1$
$11$ | $3$ | $4$ | $\frac{8+4a+a^{2}}{16}$ | $\frac{8+4a+a^{2}}{16-a^{3}}$ | $-\frac{29}{11}$ | $-\frac{53}{109}$
$12$ | $2$ | $4$ | $\frac{2+a}{16}$ | $\frac{2+a}{16-a^{2}}$ | $\frac{5}{7}$ | $-\frac{7}{9}$
$13$ | $3$ | $4$ | $\frac{8+2a+a^{2}}{16}$ | $\frac{8+2p+a^{2}}{16-a^{3}}$ | $-\frac{23}{11}$ | $-\frac{43}{109}$
$14$ | $3$ | $4$ | $\frac{4+2a+a^{2}}{16}$ | $\frac{4+2a+a^{2}}{16-a^{3}}$ | $\frac{19}{7}$ | $-\frac{39}{109}$

As per the Correspondence Theorem, note that the integer values attained by
$\chi_{3}\left(B_{2}\left(n\right)\right)$ and
$\chi_{5}\left(B_{2}\left(n\right)\right)$ are all periodic points of the maps
$T_{3}$ and $T_{5}$, respectively; this includes fixed points at negative
integers, as well. Examining $\chi_{a}\left(B_{2}\left(n\right)\right)$, we
see certain patterns, such as:

$\chi_{a}\left(B_{2}\left(2^{n}-1\right)\right)=\frac{1}{2-a},\textrm{
}\forall n\in\mathbb{N}_{1}$ (62)

More significantly, $\chi_{3}\left(B_{2}\left(n\right)\right)$ appears to be
more likely to be positive than negative, whereas the opposite appears to hold
true for $a=5$ (and, heuristically, for all odd integers $a\geq 5$). Of
special interest, however, is the example of:

$\chi_{a}\left(B_{2}\left(10\right)\right)=\frac{4+a}{16-a^{2}}=\frac{1}{4-a}$
(63)

By the Correspondence Theorem, every cycle $\Omega\subseteq\mathbb{Z}$ of
$T_{a}$ with $\left|\Omega\right|\geq 2$ contains an integer $x$ of the form:

$x=\chi_{a}\left(B_{2}\left(n\right)\right)=\frac{\chi_{a}\left(n\right)}{1-\frac{a^{\\#_{2:1}\left(n\right)}}{2^{\lambda_{2}\left(n\right)}}}=\frac{2^{\lambda_{2}\left(n\right)}\chi_{a}\left(n\right)}{2^{\lambda_{2}\left(n\right)}-a^{\\#_{2:1}\left(n\right)}}$
(64)

for some $n\in\mathbb{N}_{1}$; in fact, every periodic point $x$ of $T_{a}$ in
the odd integers can be written in this form. As such
$\left|2^{\lambda_{2}\left(n\right)}-a^{\\#_{2:1}\left(n\right)}\right|=1$ is
a _sufficient condition_ for $\chi_{a}\left(B_{2}\left(n\right)\right)$ to be
a periodic point of $T_{a}$. However, as the $n=10$ case shows, this is not __
a _necessary_ condition: there can be values of $n$ (such as $n=10$) where
$\left|2^{\lambda_{2}\left(n\right)}-a^{\\#_{2:1}\left(n\right)}\right|$ is
large, and yet, nevertheless divides the numerator on the right-hand side of
(64), reducing $\chi_{a}\left(B_{2}\left(n\right)\right)$ to an integer. In
fact, thanks to P. Mihăilescu’s resolution of Catalan’s Conjecture, it would
seem that Baker’s Method-style estimates on the _archimedean_ size of
$2^{\lambda_{2}\left(n\right)}-a^{\\#_{2:1}\left(n\right)}$ will be of limited
use in efforts to understand $\chi_{a}\left(B_{2}\left(n\right)\right)$.

29 - Mihăilescu’s Theorem[3]: The only choice of $x,y\in\mathbb{N}_{1}$ and
$m,n\in\mathbb{N}_{2}$ for which:

$x^{m}-y^{n}=1$ (65)

are $x=3$, $m=2$, $y=2$, $n=3$ (that is, $3^{2}-2^{3}=1$).

With Mihăilescu’s Theorem, it is easy to see that for any odd integer $a\geq
3$, $\left|a^{\\#_{2:1}\left(n\right)}-2^{\lambda_{2}\left(n\right)}\right|$
will never be equal to $1$ for any $n\geq 8$, because the exponent of $2$
(that is, $\lambda_{2}\left(n\right)$) will be $\geq 4$ for all $n\geq 8$ (any
such $n$ has $4$ or more binary digits). Consequently, for any odd integer
$a\geq 3$, if $n\geq 8$ makes $\chi_{a}\left(B_{2}\left(n\right)\right)$ into
a rational integer (and hence, a periodic point of $T_{a}$), it _must_ be that
the numerator $2^{\lambda_{2}\left(n\right)}\chi_{a}\left(n\right)$ in (64) is
a multiple of $2^{\lambda_{2}\left(n\right)}-a^{\\#_{2:1}\left(n\right)}$.

The set of maps of the form (1) for which conclusions of this sort hold can be
enlarged in several ways. First, in general, note that we have:

$\chi_{H}\left(B_{\varrho}\left(n\right)\right)=\frac{\chi_{H}\left(n\right)}{1-M_{H}\left(n\right)}=\frac{\varrho^{\lambda_{\varrho}\left(n\right)}\chi_{H}\left(n\right)}{\varrho^{\lambda_{\varrho}\left(n\right)}\left(1-M_{H}\left(n\right)\right)}=\frac{\varrho^{\lambda_{\varrho}\left(n\right)}\chi_{H}\left(n\right)}{\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}}$
(66)

If $\mu_{0}=1$ and there is an integer $\mu\geq 2$ so that
$\mu_{1},\ldots,\mu_{\varrho-1}$ are all positive integer powers of $\mu$
(i.e., for each $j\in\left\\{1,\ldots,\varrho-1\right\\}$ there is an
$r_{j}\in\mathbb{N}_{1}$ so that $\mu_{j}=\mu^{r_{j}}$) then, when $n\geq 1$,
the denominator of the right-hand side takes the form $\varrho^{a}-\mu^{b}$
for some positive integers $a$ and $b$ depending solely on $n$. By
Mihăilescu’s Theorem, the only way to have
$\left|\varrho^{a}-\mu^{b}\right|=1$ is for either
$\varrho^{a}-\mu^{b}=3^{2}-2^{3}$ or $\varrho^{a}-\mu^{b}=2^{3}-3^{2}$. As
such, for this case, once $n$ is large enough so that both $a$ and $b$ are
$\geq 3$, the only way for $\chi_{H}\left(B_{\varrho}\left(n\right)\right)$ to
be a rational integer for such an $n$ is if
$\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}$
is a divisor of the integer
$\varrho^{\lambda_{\varrho}\left(n\right)}\chi_{H}\left(n\right)$ of magnitude
$\geq 2$.

In the most general case, if we allow the $\mu_{j}$ to take on different
values (while still requiring $H$ to be basic so that the Correspondence
Theorem applies), in order to replicate the application of Mihăilescu’s
Theorem to the $\varrho^{a}-\mu^{b}$ case, examining the the denominator term
$\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}$
from (66) and ’de-parameterizing’ it, the case where the denominator reduces
to $1$ or $-1$ can be represented by a Diophantine equation of the form:

$\left|x^{m}-y_{1}^{n_{1}}y_{2}^{n_{2}}\cdots y_{J}^{n_{J}}\right|=1$ (67)

where $J$ is a fixed integer $\geq 2$, and $x$, $y_{1},\ldots,y_{J}$, $m$, and
$n_{1},\ldots,n_{J}$ are positive integer variables. For any fixed choice of
$x,y_{1},\ldots,y_{J}$ (where we identify $x$ with $\varrho$ and the $y_{j}$s
with the $\mu_{j}$s), if it can be shown that (67) holds for only finitely
many choices of $m$ and the $n_{j}$s, it then follows that the corresponding
case for
$\left|\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}\right|$
is not equal to $1$ for all sufficiently large positive integers $n$. In that
case, any cycles of $H$ not accounted for by values of $n$ for which
$\left|\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}\right|=1$
must necessarily occur as a result of
$\left|\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}\right|$
being an integer $\geq 2$ which divides
$\varrho^{\lambda_{\varrho}\left(n\right)}\chi_{H}\left(n\right)$.

In light of this, rather than the archimedean/euclidean _size_ of
$\varrho^{\lambda_{\varrho}\left(n\right)}-\prod_{j=0}^{\varrho-1}\mu_{j}^{\\#_{\varrho:j}\left(n\right)}$,
it appears we must study its _multiplicative_ structure, as well as that of
$\varrho^{\lambda_{\varrho}\left(n\right)}\chi_{H}\left(n\right)$—which is to
say, the set of these integers’ prime divisors, and how this set depends on
$n$. In other words, we ought to study the $p$-adic absolute values of
$\left|\chi_{H}\left(n\right)\right|_{p}$ and
$\left|1-M_{H}\left(n\right)\right|_{p}$ for various values of $n\geq 1$ and
primes $p$. It may also be of interest to use $\varrho$-adic methods (Fourier
series, Mellin transform) to study
$\left|\chi_{H}\left(\mathfrak{z}\right)\right|_{p}$ as a real-valued function
of a $\varrho$-adic integer variable for varying values of $p$.

##  4 Future Work

The origins of the present paper lie in work the author did in late 2019 and
early 2020. Around the same time, in late 2019, Tao published a paper on the
Collatz Conjecture that applied probabilistic techniques in a novel way, by
use of what Tao called “Syracuse Random Variables”[19]. Despite the many
substantial differences between these two approaches (Tao’s is probabilistic,
ours is not), they are linked at a fundamental level, thanks to the function
$\chi_{3}$—our shorthand for $\chi_{T_{3}}$, the $\chi_{H}$ associated to the
Shortened Collatz map. Given that both papers have their genesis in an
examination of the behavior of different combinations of the iterates of
branches of $T_{3}$, it is not entirely surprising that both approaches led to
$\chi_{3}$.

Tao’s approach involves constructing his Syracuse Random Variables and then
comparing them to a set-up involving tuples of geometric random variables, the
comparison in question being an estimate on the ’distance’ between the
Syracuse Random Variables and the geometric model, as measured by the total
variation norm for discrete random variables. The central challenge Tao
overcomes to obtain these results is to establish explicit estimates for the
decay of the characteristic function of the Syracuse Random Variables. In our
terminology, Tao provides an estimate for the absolute value of the function:

$\varphi_{3}\left(t\right)\overset{\textrm{def}}{=}\int_{\mathbb{Z}_{2}}e^{-2\pi
i\left\\{t\chi_{3}\left(\mathfrak{z}\right)\right\\}_{3}}d\mathfrak{z},\textrm{
}\forall t\in\hat{\mathbb{Z}}_{3}$ (68)

as $t$ varies, where $\left\\{\cdot\right\\}_{3}$ is the $3$-adic fractional
part, $d\mathfrak{z}$ is the Haar probability measure on $\mathbb{Z}_{2}$, and
$\hat{\mathbb{Z}}_{3}=\mathbb{Z}\left[\frac{1}{3}\right]/\mathbb{Z}=\mathbb{Q}_{3}/\mathbb{Z}_{3}$
is the Pontryagin dual of $\mathbb{Z}_{3}$, identified here with the set of
all rational numbers in $\left[0,1\right)$ whose denominators are non-negative
integer powers of the prime number $3$. Tao’s decay estimate is given in
Proposition 1.17 of his paper, where the above integral appears in the form of
an expected value[19].

With this in mind, a natural next step for furthering both this paper and
Tao’s would be to study the “characteristic function” of $\chi_{H}$ for an
arbitrary semi-basic $H$; this is the continuous function
$\varphi_{H}:\hat{\mathbb{Z}}_{q_{H}}\rightarrow\mathbb{C}$ defined by:

$\varphi_{H}\left(t\right)\overset{\textrm{def}}{=}\int_{\mathbb{Z}_{\varrho}}e^{-2\pi
i\left\\{t\chi_{H}\left(\mathfrak{z}\right)\right\\}_{q_{H}}}d\mathfrak{z},\textrm{
}\forall t\in\hat{\mathbb{Z}}_{q_{H}}$ (69)

where $\left\\{\cdot\right\\}_{q_{H}}$ is the $q_{H}$-adic fractional part,
$d\mathfrak{z}$ is the Haar probability measure on $\mathbb{Z}_{\varrho}$, and
$\hat{\mathbb{Z}}_{q_{H}}=\mathbb{Z}\left[\frac{1}{q_{H}}\right]/\mathbb{Z}=\mathbb{Q}_{q_{H}}/\mathbb{Z}_{q_{H}}$
is the Pontryagin dual of $\mathbb{Z}_{q_{H}}$, identified here with the set
of all rational numbers in $\left[0,1\right)$ whose denominators are non-
negative integer powers of $q_{H}$. (Note, we do not require either of
$\varrho$ or $q_{H}$ to be primes.)

Functional equations for $\varphi_{H}$ can be easily established with a little
bit of $p$-adic integration.

30 - Proposition: Let $H$ be semi-basic, and write $q=q_{H}$. Then, the
characteristic function
$\varphi_{H}:\hat{\mathbb{Z}}_{q}\rightarrow\mathbb{C}$ defined by (69)
satisfies the functional equation:

$\varphi_{H}\left(t\right)=\frac{1}{\varrho}\sum_{j=0}^{\varrho-1}e^{-2\pi
i\left\\{\frac{b_{j}t}{d_{j}}\right\\}_{q}}\varphi_{H}\left(\frac{a_{j}t}{d_{j}}\right),\textrm{
}\forall t\in\hat{\mathbb{Z}}_{q}$ (70)

_Remark_ : Since $H$ is semi-basic, 15 tells us that all of the $d_{j}$s are
co-prime to $q$. Thus, the multiplication-by-$d_{j}$ map $t\mapsto d_{j}t$ is
a group automorphism of $\hat{\mathbb{Z}}_{q}$, and as such, $b_{j}t/d_{j}$
and $a_{j}t/d_{j}$ denote the images of $b_{j}t$ and $a_{j}t$, respectively,
under the inverse of this automorphism. One can remove the denominator terms
if one wishes by writing
$d=\textrm{lcm}\left(d_{0},\ldots,d_{\varrho-1}\right)$,
$d_{j}^{\prime}=d/d_{j}$, $\alpha_{j}=a_{j}d_{j}^{\prime}$,
$\beta_{j}=b_{j}d_{j}^{\prime}$ (note that
$d,d_{j}^{\prime},\alpha_{j},\beta_{j}$ are all integers) and then replacing
$t$ with $dt$ in (70); this yields:

$\varphi_{H}\left(dt\right)=\frac{1}{\varrho}\sum_{j=0}^{\varrho-1}e^{-2\pi
i\beta_{j}t}\varphi_{H}\left(\alpha_{j}t\right),\textrm{ }\forall
t\in\hat{\mathbb{Z}}_{q}$ (71)

Proof: The proof is a straight-forward computation. Details regarding Fourier
analysis on $\varrho$-adic rings can be found in [6].

Q.E.D.

The Fourier analysis here naturally leads to probabilistic notions. For any
measurable function $f:\mathbb{Z}_{\varrho}\rightarrow\mathbb{Z}_{q}$, any
$n\in\mathbb{N}_{0}$ and any $m\in\mathbb{Z}$, we write:

$\textrm{P}\left(f\overset{q^{n}}{\equiv}m\right)\overset{\textrm{def}}{=}\int_{\mathbb{Z}_{\varrho}}\left[f\left(\mathfrak{z}\right)\overset{q^{n}}{\equiv}m\right]d\mathfrak{z}$
(72)

where $d\mathfrak{z}$ is the Haar probability measure on
$\mathbb{Z}_{\varrho}$ and
$\left[f\left(\mathfrak{z}\right)\overset{q^{n}}{\equiv}m\right]$ is $1$ if
$f\left(\mathfrak{z}\right)$ is congruent to $m$ mod $q^{n}$ and is $0$
otherwise; for brevity, here, we shall write a congruence $x=y\mod a$ as
$x\overset{a}{\equiv}y$. Also, we adopt the convention that
$\mathfrak{x}\overset{1}{\equiv}\mathfrak{y}$ is true for any $q$-adic
integers $\mathfrak{x}$ and $\mathfrak{y}$. As such:

$\textrm{P}\left(f\overset{q^{0}}{\equiv}m\right)=\textrm{P}\left(f\overset{1}{\equiv}m\right)=\int_{\mathbb{Z}_{\varrho}}\left[f\left(\mathfrak{z}\right)\overset{1}{\equiv}m\right]d\mathfrak{z}=\int_{\mathbb{Z}_{\varrho}}d\mathfrak{z}=1$

for any $f$ and any $m$. In probabilistic language, the $\sigma$-algebra of
events is the $\sigma$-algebra of Haar-measurable subsets of
$\mathbb{Z}_{\varrho}$, and the function $f$ is a $\mathbb{Z}_{q}$-valued
random variable.

Fourier relations follow from the identity:

$\left[\mathfrak{x}\overset{q^{n}}{\equiv}\mathfrak{y}\right]=\frac{1}{q^{n}}\sum_{k=0}^{q^{n}-1}e^{2\pi
i\left\\{k\frac{\mathfrak{x}-\mathfrak{y}}{q^{n}}\right\\}_{q}},\textrm{
}\forall n\in\mathbb{N}_{0},\textrm{
}\forall\mathfrak{x},\mathfrak{y}\in\mathbb{Z}_{q}$ (73)

where, again, we are employing Iverson Bracket notation:
$\left[\mathfrak{x}\overset{q^{n}}{\equiv}\mathfrak{y}\right]=1$ if
$\mathfrak{x}\overset{q^{n}}{\equiv}\mathfrak{y}$ is true, and $0$ otherwise.
This gives us the typical Fourier relations between probabilities and
characteristic functions:

$\displaystyle\textrm{P}\left(\chi_{H}\overset{q^{n}}{\equiv}m\right)$
$\displaystyle=\frac{1}{q^{n}}\sum_{k=0}^{q^{n}-1}e^{-\frac{2\pi
ikm}{q^{n}}}\varphi_{H}\left(\frac{k}{q^{n}}\right)$ (74)
$\displaystyle\varphi_{H}\left(\frac{m}{q^{n}}\right)$
$\displaystyle=\sum_{k=0}^{q^{n}-1}e^{\frac{2\pi
imk}{q^{n}}}\textrm{P}\left(\chi_{H}\overset{q^{n}}{\equiv}k\right)$ (75)

and the Parseval Identity:

$\frac{1}{q^{n}}\sum_{k=0}^{q^{n}-1}\left|\varphi_{H}\left(\frac{k}{q^{n}}\right)\right|^{2}=\sum_{k=0}^{q^{n}-1}\left(\textrm{P}\left(\chi_{H}\overset{q^{n}}{\equiv}k\right)\right)^{2}$
(76)

Under certain circumstances (such as the case when $H$ is a $T_{a}$ map), one
can use (70) to solve recursively for $\varphi_{H}$—or, equivalently, for
$\textrm{P}\left(\chi_{H}\overset{q^{n}}{\equiv}k\right)$, after performing a
discrete Fourier transform to (70) or (71). Doing so for $H=T_{3}$ yields the
recursive formula given by Tao in Lemma 1.12 of his paper[19]. Additionally,
toward the end of understanding the behavior
$\left|\chi_{H}\left(n\right)\right|_{p}$ as $n$ varies, where $p$ is an
arbitrary prime. That being said, it remains to be seen whether or not
recursive formulae can be derived for these probabilities and characteristic
functions in the case of a general semi-basic $H$. It may also be of interest
to study the expressions
$\varphi_{H,p}:\hat{\mathbb{Z}}_{p}\rightarrow\mathbb{C}$ given by:

$\varphi_{H,p}\left(t\right)\overset{\textrm{def}}{=}\int_{\mathbb{Z}_{\varrho}}e^{-2\pi
i\left\\{t\chi_{H}\left(\mathfrak{z}\right)\right\\}_{p}}d\mathfrak{z}\overset{\textrm{def}}{=}\lim_{N\rightarrow\infty}\frac{1}{\varrho^{N}}\sum_{n=0}^{\varrho^{N}-1}e^{-2\pi
i\left\\{t\chi_{H}\left(n\right)\right\\}_{p}},\textrm{ }\forall
t\in\hat{\mathbb{Z}}_{p}$ (77)

where $p$ is an arbitrary prime; one might also consider the sum on the right
for fixed large $N$, rather than letting $N\rightarrow\infty$

In addition to these approaches, one can use techniques of $\varrho$-adic
Fourier analysis to investigate $\chi_{H}$ by considering truncations of the
form: $\chi_{H,N}:\mathbb{Z}_{\varrho}\rightarrow\mathbb{R}$ defined by:

$\chi_{H,N}\left(\mathfrak{z}\right)=\sum_{n=0}^{\varrho^{N}-1}\chi_{H}\left(n\right)\left[\mathfrak{z}\overset{\varrho^{N}}{\equiv}n\right],\textrm{
}\forall\mathfrak{z}\in\mathbb{Z}_{\varrho},\textrm{ }\forall N\geq 1$ (78)

where $\left[\mathfrak{z}\overset{\varrho^{N}}{\equiv}n\right]$ is $1$ when
the $\varrho$-adic integer $\mathfrak{z}$ is congruent to $n$ modulo
$\varrho^{N}$ and is zero, otherwise. Additionally, one can employ classical
complex-analytic methods (Perron’s Formula, Mellin Inversion, etc.) to study
the Dirichlet generating functions for the sequences
$\left\\{\chi_{H}\left(n\right)\right\\}_{n\geq 0}$ and
$\left\\{1-M_{H}\left(n\right)\right\\}_{n\geq 0}$. Using Perron’s formula and
the like, one can use the identity
$\left(1-M_{H}\left(n\right)\right)x-\chi_{H}\left(n\right)=0$ (obtained by
re-writing the equations from 26) to re-formulate the question of periodic
points of $H$ in terms of a contour integral. The author intends to pursue
these and other lines of inquiry in future publications.

## References

  * [1] A. Baker, _Transcendental number theory_ , Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Cambridge, 1990
  * [2] C. Böhm and G. Sontacchi, _On the existence of cycles of given length in integer sequences like $x_{n}+1=x_{n}/2$ if $x_{n}$ even, and $x_{n+1}=3x_{n}+1$ otherwise_, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. 64 (1978), 260–264.
  * [3] H. Cohen, _Number theory: Volume II: Analytic and modern tools_ (Vol. 240). Springer Science & Business Media, 2008
  * [4] K. Conrad, _Infinite Series in $p$-Adic Fields_, <https://kconrad.math.uconn.edu/blurbs/gradnumthy/infseriespadic.pdf>
  * [5] M. R. Feix, M. Muriel and J. L. Rouet, _Statistical Properties of an Iterated Arithmetic Mapping_ , J. Stat. Phys., 76 (1994), 725-741
  * [6] D. Goldfeld and J. Hundley, _Automorphic Representations and L-Functions for the General Linear Group: Volume 1_ , Vol. 129, Cambridge University Press, Cambridge, 2011
  * [7] A. V. Kontorovich and J. C. Lagarias, _Stochastic Models for the 3x+1 and 5x+1 Problems_ ”, 2009 <https://arxiv.org/pdf/0910.1944>
  * [8] A. V. Kontorovich and Y. G. Sinai, _Structure Theorem for $\left(d,g,h\right)$-Maps_”, 2006 <https://arxiv.org/pdf/math/0601622.pdf>
  * [9] J. C. Lagarias, _The $3x+1$ problem and its generalizations_, Amer. Math. Monthly 92 (1985), 3–23.
  * [10] G. M. Leigh, _A Markov process underlying the generalized Syracuse algorithm_ , Acta Arith. 46 (1986) 125-143.
  * [11] K. R. Matthews, _A Generalized $3x+1$ Conjecture_, <https://www.numbertheory.org/gnubc/challenge>
  * [12] K. R. Matthews, _The generalized $3x+1$ mapping: George Leigh’s approach_, <http://www.numbertheory.org/keith/george.html>
  * [13] K. R. Matthews, _Generalizations of the $3x+1$ problem and connections with Markov matrices and chains_, 2010 <http://www.numbertheory.org/PDFS/3x+1_slides.pdf>
  * [14] K. R. Matthews and A. M. Watts, _A Markov approach to the generalized Syracuse algorithm_. Acta Arith. 45(1), (1985) 29-42.
  * [15] A. M. Robert, _A course in p-adic analysis_ (Vol. 198). Springer Science & Business Media, Chicago, 2013
  * [16] O. Rozier, “ _Parity sequences of the $3x+1$ map on the $2$-adic integers and Euclidean embedding_”, 2018 <https://arxiv.org/pdf/1805.00133.pdf>
  * [17] W. Schikhof, _Ultrametric Calculus: An Introduction to p-Adic Analysis_ (Cambridge Studies in Advanced Mathematics), Cambridge University Press, Cambridge, 1985
  * [18] T. Tao, _The Collatz conjecture, Littlewood-Offord theory, and powers of $2$ and _$3$, 2011 <https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/>
  * [19] T. Tao, _Almost all orbits of the Collatz map attain almost bounded values_ , 2019 <https://arxiv.org/pdf/1909.03562.pdf>
  * [20] R. Terras, _A stopping time problem on the positive integers_ , Acta Arith. XXX, 1976
  * [21] R. Terras, _On the existence of a density_ , Acta Arith. XXXV, 1979