# Bounded Trajectories of the $3x+\gamma$ Problem

Benjamin Bairrington

(June 2023)

## Abstract

The $3x+1$ Problem was first formally presented during the 1950 International
Congress of Mathematics[17] by Dr. Collatz. In this thesis, we study the
bounded trajectories of the $3x+\gamma$ Problem, which is a generalization of
the $3x+1$ Problem. Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and
$n\in\mathbb{Z}_{>0}$. We define the function
$C_{\gamma}:{\mathbb{Z}}_{>0}\to{\mathbb{Z}}_{>0}$ such that if $n$ is odd,
$C_{\gamma}(n)=3n+\gamma$; and if $n$ is even, $C_{\gamma}(n)=n/2$. We call
the sequence $\\{n,C_{\gamma}(n),C_{\gamma}^{2}(n),\cdots\\}$ a trajectory of
$n$. The Collatz conjecture says that for any $n\in{\mathbb{Z}}_{>0}$, there
exists $k\in{\mathbb{Z}}_{>0}$ such that $C_{1}^{k}(n)=1$. We define the
characteristic mapping $\chi_{\gamma}:{\mathbb{Z}}_{>0}\to\\{0,\,1\\}$ to be
$\chi_{\gamma}(n)\equiv C_{\gamma}(n)\,{\rm mod}\,2$. The sequence generated
by compositions of $\chi_{\gamma}$ acting on $n$ is called the characteristic
trajectory associated to $n$. Assume that the trajectory of $n$ is bounded
above. Then there exists some $n^{\prime}$ contained in the trajectory and the
smallest $N$ in $\mathbb{Z}_{>0}$ such that
$C_{\gamma}^{N}(n^{\prime})=n^{\prime}$. We call sequence
$\\{n^{\prime}=C_{\gamma}^{0}(n^{\prime}),\,C_{\gamma}(n^{\prime}),\cdots,C_{\gamma}^{N-1}(n^{\prime})\\}$
an integral loop of length $N$ starting at $n^{\prime}$ and associated with
the $3x+\gamma$ Problem. The existence of an integral loop other than
$\\{1,4,2\\}$ would be a counterexample of the Collatz Conjecture.

Let $n$ start an integral loop of length $N$ associated with the $3x+\gamma$
Problem. Let $\rho$ and $\nu$ be the count of the number of zeros and ones in
a single period of $B=\left(\chi_{\gamma}^{i}(n)\right)_{i\geq 0}$. In a
single period of $B$, let $m_{j}$ denote the number of zeros between the
$(j-1)$th and $j$th one. Let $\mathcal{M}_{n}$ be the matrix associated to $n$
whose elements are the sequential products of $2^{m_{j}}$ (e.g.
$(2^{m_{0}},2^{m_{0}+m_{1}},2^{m_{0}+m_{1}+m_{2}},...)$). Let $p$ be a prime
factor for all the terms in the integral loop starting with $n$ with
multiplicity $a>0$. Suppose also that $p$ is a prime factor of $\gamma$ and
$2^{\rho}-3^{\nu}$ with multiplicity $b$ and $c$, respectively. Finally assume
that $c>b-a$. Then $\det(\mathcal{M}_{n})\equiv 0\pmod{p}$. We do find
examples of this property. Let $\nu$ be prime. Let
$z_{j}=2^{(m_{j}+2m_{j+1}+3m_{j+2}+...)/\nu}$ be a weighted arithmetic average
of the $m_{j}$. We prove that if $p$ is a prime factor of $2^{\rho}-3^{\nu}$
distinct from $\nu$ so that the residue class $p\pmod{\nu}$ generates the
whole group $\mathbb{Z}_{\nu}^{*}$ then $p\nmid\det(\mathcal{M}_{n})$ if and
only if $p\nmid(z_{1}+...+z_{\nu})$ and for any $1\leq i<j\leq\nu$ we have
$z_{i}\not\equiv z_{j}\pmod{p}$. By this, we give an interesting property for
the integral loop.

Keywords: Integral Loops, Trajectories, Characteristic Trajectories, Circulant
Matrix, Number Theoretic Functions, $3x+1$ Problem.

##  Chapter 1 Introduction

###  1.1 Organization of This Thesis

The chapters of this thesis are organized to direct the reader to Theorem
3.3.9. Chapter one provides the historical, contemporary, and current research
into the $3x+1$ Problem. It closes by presenting a summary of the key results
found, as well as relevant notation. Chapter two presents the Integral Loop
Formula in Equation (2.4) and the integral loop vector in Equation (2.5). The
integral loop vector is the primary mathematical tool used throughout this
thesis. Chapter three focuses on presenting the Integral Loop Formula in terms
of the matrix $\mathcal{M}_{n}$ given in Definition 3.5. We find that the the
integral loop vector is the solution to the matrix product presented in
Equation (3.6). We find the associated circulatant matrix $\mathcal{R}_{n}$
whose determinant, up to a sign change, is identical to $\mathcal{M}_{n}$.
Finally, this property was exploited yielding the result of Theorem 3.3.9.
Chapter four explores some additional topics related to the findings here, but
were not suitable for the thesis proper.

###  1.2 Historical Background

The story of the $3x+1$ Problem formally begins at the 1950 International
Congress of Mathematics with its creator: Dr. Collatz[17]. At the Congress,
Dr. Collatz told many of his colleagues about the $3x+1$ Problem. Most notably
were Dr. Coxeter, Dr. Kakutani, and Dr. Ulam [18]. In 1952 Dr. Brian Thwaites
independently created the $3x+1$ Problem [17]. Additionally in 1952, Dr.
Collatz accepted a position at Hamburg University and presented the $3x+1$
Problem to his colleague Dr. Hasse [30]. It is through these four (Dr.
Coxeter, Dr. Kakutani, Dr. Ulam, and Dr. Hasse) that the problem would spread
by word of mouth to many academic institutions worldwide. This process began
when Dr. Hasse presented the $3x+1$ Problem to Syracuse University, leading to
the nick-names The Syracuse Problem as well as Hasse’s Algorithm [18]. In 1960
Dr. Kakutani presented the problem at Yale and the University of Chicago
leading to the nick-name Kakutani’s Problem [17]. From there it went to the
Massachusetts Institute of Technology where the $3x+1$ Problem was checked for
all starting values less than sixty million [10].

It was not until 1971 when the $3x+1$ Problem first appeared in print in a set
of memorial lecture notes by Dr. H.S.M. Coxeter [6]. Nevertheless, it remained
an underground problem appearing as a novelty in Scientific American in 1972
[10]. In 1975 Dr. Hasse wrote about the problem [11], again putting it into
print. In the mid-seventies Dr. Ulam spread the problem to Los Alamos National
Laboratory [18] where it was received by Dr. Everett who wrote about the
problem in 1977 [9]. Around this time the $3x+1$ Problem become an
internationally known problem. The $3x+1$ Problem remained unsolved to this
day.

###  1.3 Modern Progress

######  Definition 1.3.1.

The following mappings $C$ (Collatz) and $T$ ($3x+1$) map the integers to the
integers in the following form:

$\begin{aligned} C(n)&:=\left\\{\begin{array}[]{ll}3n+1,n\equiv 1\pmod{2},\\\
\frac{n}{2},n\equiv 0\pmod{2}\end{array}\right.\end{aligned},\begin{aligned}
T(n)&:=\left\\{\begin{array}[]{ll}\frac{3n+1}{2},n\equiv 1\pmod{2},\\\
\frac{n}{2},n\equiv 0\pmod{2}\end{array}\right.\end{aligned}.$ (1.1)

The conjecture regarding either $T$ or $C$ is whether for every positive
integer $n$, there exists a positive integer $k$ such that $C^{k}(n)=1$, or
$T^{k}(n)=1$, respectively. This makes the conjecture a $\Pi_{2}$ statement
that can be written in the form: $(\forall n)(\exists k)(C^{k}(n)=1)$ [23].

There are variants of ‘Collatz-like’ problems that are sufficiently complex to
be considered undecidable. Fix $p\in\mathbb{Z}_{\geq 2}$ and
$a_{0},b_{0},...a_{p-1},b_{p-1}\in\mathbb{Q}$. We call a function
$g:\mathbb{Z}\rightarrow\mathbb{Z}$ a generalized Collatz mapping[23] if for
all $i$, $0\leq i\leq p-1$, and all $n\in\mathbb{Z}$,

$g(n)=a_{i}n+b_{i},\text{ if }n\equiv i\pmod{p}.$ (1.2)

In this definition of $g$, $a_{i},b_{i}$ are chosen so that $a_{i}n+b_{i}$ is
always integral when $n\equiv i\pmod{p}$. Conway proved that given a function
$g$ and an integer $n$, there exists no algorithm which determines if there
exists positive integer $k$ such that $g^{k}(n)=1$ [29][23][5]. This question
was demonstrated to be undecidable by comparing it to fractional-linear
mapping similar to Equation (1.2) with all $b_{i}=0$ [5] [23]. The fractional-
linear mapping itself is undecidable because it is a special case of the
FRACTRAN algorithm, which had been demonstrated to be a universal computer
[23].

Now consider a second kind of generalization. Fix $p\in\mathbb{Z}_{>0}$ and
$a_{0},b_{0},...,a_{p-1},b_{p-1}\in\mathbb{Q}$. We call a function
$h:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ a Collatz-type iteration
function [25] if for all $i$, $0\leq i\leq p-1$ and all $n\in\mathbb{Z}_{>0}$,

$h(n)=\frac{a_{i}n+b_{i}}{p},\text{ if }n\equiv i\pmod{p}.$ (1.3)

In this definition of $h$, $a_{i},b_{i}$ are chosen so that
$a_{i}n+b_{i}\equiv 0\pmod{p}$. Let $n\in\mathbb{Z}_{>0}$ be given. We call
the sequence of iterations $\\{n,h(n),h^{2}(n),h^{3}(n),...\\}$ the trajectory
of $n$. Additionally, we say the trajectory of $n$ converges to an integral
loop if there exists a $k,n^{\prime}>0$ so that $n^{\prime}$ is contained in
the trajectory of $n$ and $h^{k}(n^{\prime})=n^{\prime}$. It is proven that if
$h$ distributes evenly among all of the residue classes modulo $p$, then
almost all trajectories converge to an integral loop[25].

A similar ‘Collatz-like’ mapping appears in Equation (1.4):

$\begin{aligned} f:\mathbb{Z}&\rightarrow\mathbb{Z}\\\
f(n)&=\left\\{\begin{array}[]{ll}\frac{n}{2},\text{ }n\equiv 0\pmod{2}\\\
3n+t,\text{ }n\in A_{t}\end{array}\right.\end{aligned},$ (1.4)

where $A_{t}$ is a recursive set partitioning the odd positive integers, and
$t$ = -9,-8,…,8,9 [9][20]. By encoding Turing machines into sequences
consisting of zeros and twos in base three, one can choose two integers in the
set $\\{-9,...,9\\}$ ensuring that when the Turing machine halts, $f$ descends
down to one without overlapping other Turing machines encoded in this
manner[20]. Thus a never halting computation is coded by a trajectory of $f$
diverging to infinity[23]. Suppose we have some algorithm that determines
whether given $n\in\mathbb{Z}_{>0}$, there exists some $k>0$ so that
$f^{k}(n)=1$. Then given a universal Turing machine, such an algorithm would
decide the halting problem for this machine. This is a contradiction[23].

Consider the characteristic mapping $\chi$ of $T$ defined below.

######  Definition 1.3.2.

The characteristic mapping $\chi$ takes $N$ iterative steps (indexed by the
variable $i$) of the $T$ mapping to a boolean variable determined by the
parity of the value of the function at each step.

$\begin{aligned} \chi_{i}(n)&=\left\\{\begin{array}[]{ll}1,\text{
}T^{i}(n)\equiv 1\pmod{2}\\\ 0,\text{ }T^{i}(n)\equiv
0\pmod{2}\end{array}\right.\\\
n&\rightarrow\\{\chi_{0},\chi_{1},\chi_{2},...,\chi_{N-1}\\}\end{aligned}.$
(1.5)

Induction can prove that the binary sequence of length $N$ is unique for
integers $n<2^{N}$ [9]. Hence, there exists an injective mapping between the
integers $n<2^{N}$ and binary sequences of length $N$ [9]. Furthermore from a
statistical standpoint, for every $n<2^{N}$, the probability that each
inductive step of $\chi_{i}$ being a 1 or 0 approaches one-half (like a coin
flip) for large $N$ [8]. This property allows for the exploration of an
‘average growth rate’ of the $T$ mapping. The average growth rate of a
trajectory where $N-1$ odd numbers appears converges to 3/4 as $N$ goes to
infinity [29]. It is shown that for the starting integers $n$ for which a
value less than $n^{\ln(3)/\ln(4)}$ is reached after a finite number of steps
along the trajectory of $n$ has an asymptotic density of 1 [16].

###  1.4 Current Developments in Research

In the last twenty years, even further progress has been made with respect to
the $3x+1$ Problem. Oftentimes, this progress is made by considering further
generalizations of the original question. Let $p$ and $g$ be coprime integers
with $g>p\geq 2$. Let $h(x)$ be a periodic function satisfying: $h(x+p)=h(x)$,
$x+h(x)\equiv 0\pmod{p}$, and $0<|h(x)|<g$ for all $x$ not divisible by $p$.
Then consider the following mapping of the integers to the integers,

$\tilde{T}(x)=\frac{gx+h(gx)}{p^{k}},$ (1.6)

where $k$ is uniquely chosen so that the result is not divisible by $p$. It
can be shown that for maps of this form [15] infinity is either a point of
convergence or a repelling point of the typical trajectory. That is to say a
typical trajectory returns to the origin if $\log(g)-\frac{p}{p-1}\log(p)<0$.

The $3x+1$ Problem can also be classified in the collection of Residue-Class-
Wise Affine functions [14]. A mapping $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is
called Residue-Class-Wise Affine if there is a positive integer $m$ such that
$f$ is affine on the residue classes modulo $m$. Let the smallest such $m$ be
the referred to as the modulus of $f$ and write Mod($f$). Additionally, $f$ is
called tame if the set $\\{\text{Mod}(f^{(k)})|k\in\mathbb{Z}_{>0}\\}$ is
bounded, and wild otherwise. In this context, the $3x+1$ mapping T can be
shown to be wild[14].

Another emerging occurrence of the $3x+1$ Problem is in Computational Theory.
In fact, it is proven[21] that the $3x+1$ Conjecture is true if and only if
for all positive integers (written in base three), there exists an $n\geq 0$
so that Turing Machine $M_{1}$[21] eventually reaches the configuration
${}^{\omega}b0^{n}(A1)b^{\omega}$.

This is not a unique occurrence. Collatz-like functions have their place in
theories regarding the Busy Beaver Game. Consider the collection of all Turing
Machines with $n$ states (not including the halting state) and two symbols
(not including the blank symbol) initialized on a completely blank tape that
halts after a finite number of steps. Let $S(n)$ denote the maximum number of
computation steps made by each machine before halting, and $\Sigma(n)$ the
maximum number of symbols 1 left remaining [22]. It has been proven that $S$
and $\Sigma$ are non-computable functions, so that for any computable function
$f$ there exists an integer $N$ such that for all $n\geq N$,
$S(n)>\Sigma(n)>f(n)$ [22]. Some, but not all of these machines reach the
maximum value of $S(n)$ by simulating Collatz-like functions on their input.
It is hypothesized [2] that progress on the Collatz Conjecture and Collatz-
like functions go hand in hand with progress on determining the Busy Beaver
champions.

Last, but certainly not least was the development regarding the density of
orbits under the $3x+1$ mapping. Let $N\in\mathbb{Z}_{>0}$ be given. Let
$C_{min}(N)=min_{i\geq 0}\\{C^{i}(N)\\}$. It was shown [27] that for any
function $f:\mathbb{Z}_{>0}\rightarrow\mathbb{R}$ with the property
$\lim_{N\rightarrow\infty}f(N)=+\infty$, we have $C_{min}(N)\leq f(N)$ for
almost all $N\in\mathbb{Z}_{>0}$.

###  1.5 This Thesis’ Contribution

One could argue that the heart of this thesis is to be the spiritual successor
of the work made by J. F. Alves, M.M. Graça, et. al[3]. Their work framed the
$3x+1$ Problem in the terms of linear algebra. They succeeded in defining the
compositions of the mapping $C$ in terms of matrix products. Here we study a
generalization of the $3x+1$ Problem, the $3x+\gamma$ Problem.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$. Let
$C_{\gamma}:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ be defined as,

$C_{\gamma}(n)=\begin{cases}3n+\gamma&\text{if }n\equiv 1\pmod{2},\\\
\frac{n}{2}&\text{if }n\equiv 0\pmod{2}.\end{cases}$ (1.7)

Furthermore, for $k\geq 0$, denote function composition as
$C_{\gamma}^{k+1}(n)=C_{\gamma}^{k}\circ C_{\gamma}(n)$ and
$C_{\gamma}^{0}(n)=n$. Let $n\in\mathbb{Z}_{>0}$ be given. Let
$\\{C_{\gamma}^{0}(n),C_{\gamma}^{1}(n),...\\}$ denote the trajectory of $n$.
Here, we consider the limiting case when a given trajectory of a positive
integer $n$ is bounded. That is to say, for $\gamma\in\mathbb{Z}_{0}^{odd}$
and $n\in\mathbb{Z}_{>0}$ given, there exists some finite $\Omega>0$ such that
the trajectory of $n$ is bounded above by $\Omega$. This necessarily implies
there exists some $n^{\prime},N\in\mathbb{Z}_{>0}$ so that $n^{\prime}$ is
contained in the trajectory of $n$ and
$C_{\gamma}^{N}(n^{\prime})=n^{\prime}$.

Fix $n\in\mathbb{Z}_{>0}$. If there exists some $N\in\mathbb{Z}_{>0}$ so that
$C_{\gamma}^{N}(n)=n$ then we say $n$ starts an integral loop. Additionally,
let $N=\min(\\{i\in\mathbb{Z}_{>0}|C_{\gamma}^{i}(n)=n\\})$ be the least
positive integer so that $C_{\gamma}^{N}(n)=n$. Then we say $n$ starts an
integral loop of length $N$.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$. Let
$\chi_{\gamma}:\mathbb{Z}_{>0}\rightarrow\\{0,1\\}$ be defined as,

$\chi_{\gamma}(n)=\begin{cases}1&\text{if }C_{\gamma}(n)\equiv 1\pmod{2},\\\
0&\text{if }C_{\gamma}(n)\equiv 0\pmod{2}.\end{cases}$ (1.8)

Let $\chi_{\gamma}^{0}(n)\equiv n\pmod{2}$. Furthermore, for $k\geq 0$, denote
function composition as $\chi_{\gamma}^{k+1}(n)=\chi_{\gamma}\circ
C_{\gamma}^{k+1}(n)$. Fix $n\in\mathbb{Z}_{>0}$. Let
$\\{\chi_{\gamma}^{0}(n),\chi_{\gamma}^{1}(n),...\\}$ denote the
characteristic trajectory of $n$.

######  Example 1.

The first eight terms of the trajectory and characteristic trajectory induced
by $n=7$ and $\gamma=1$ appears below respectively,

$\\{7,22,11,34,17,52,26,13\\}\text{ and }\\{1,0,1,0,1,0,0,1\\}.$

Let $\\{0,1\\}^{**}$ denote the set of binary sequences of infinite length.
Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. We say the
binary sequence $B\in\\{0,1\\}^{**}$ is associated to the characteristic
trajectory of $n$ if $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$.

Suppose $n$ starts an integral loop of length $N$. Then the binary sequence
$B$ associated to $n$ has a repeating period of length $N$. Let $\rho$ be the
number of zeros in a single period of $B$. Let $\nu$ be the number of ones in
a single period of $B$. Let $m_{0}$ denote the number of leading zeros. Let
$m_{j}$ denote the number of zeros between the $(j-1)$th and the $j$th one.
Let $m_{\nu}$ be the remaining zeros after the last one. Note that
$\sum_{j}m_{j}=\rho$.

######  Example 2.

The integral loop induced by $n=157$ and $\gamma=175$ appears below,

$\\{157,646,323,1144,572,286,143,604,302,151,628,314\\}.$

######  Proposition 1.5.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. Let
$B\in\\{0,1\\}^{**}$ such that $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Suppose
that $N$ is the smallest positive integer such that $C_{\gamma}^{N+1}(n)=n$.
Let $\rho$ and $\nu$ be the count of the number of zeros and ones,
respectively, in $B$ for all $i$ between $0$ and $N$ inclusive.

  1. 1.

If n is odd, let $m_{1},...,m_{v-1}$ be the number of zeros between the
$(j-1)$th and $j$th one. Let $m_{0}=0$ and $m_{\nu}$ be the remaining zeros
after the last one.

  2. 2.

If n is even, let $m_{0}$ be the number of leading zeros. Observe that
$n=2^{m_{0}}\tilde{n}$ for $\tilde{n}$ being odd. So we obtain
$m_{1},...,m_{\nu-1}$ by (1) and $\tilde{n}$.

Then $n$ satisfies the following equality

$n=\frac{\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}-3^{\nu}}.$
(1.9)

######  Remark.

Proposition 1.5.1 can be deduced as a corollary of Proposition 2.1.1.

######  Example 3.

Consider again the integral loop induced by $n=157$ and $\gamma=175$. With
respect to Equation (1.9) we find that,

$\displaystyle n$ $\displaystyle=\frac{175(3^{4-1}+3^{4-2}\times
2^{1}+3^{4-3}\times 2^{1+3}+3^{4-4}\times 2^{1+3+2})}{2^{8}-3^{4}},$
$\displaystyle=\frac{175(27+9\times 2+3\times 16+1\times 64)}{175}=157.$

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose that $n$ starts an integral loop of length $N$.
Let $i\geq 0$ be the indexing of $B$ so that $B=(\chi_{\gamma}^{i}(n))_{i\geq
0}$. Let $i_{j}$ be the sub-indexing of $i$ so that for all $0\leq
j\leq\nu-1$, we have $\chi_{\gamma}^{i_{j}}(n)\equiv 1\pmod{2}$. Note that
$i_{0}=0$. Let $e_{j}$ denote the standard basis of $\mathbb{R}^{\nu}$. We
call the array $[n]\in\mathbb{Z}^{\nu}$ the integral loop vector, which
appears in the following form:

$[n]=\begin{bmatrix}C_{\gamma}^{i_{0}}(n)\\\ C_{\gamma}^{i_{1}}(n)\\\
\vdots\\\
C_{\gamma}^{i_{\nu-1}}(n)\end{bmatrix}=\sum_{j=1}^{\nu}C_{\gamma}^{i_{j-1}}(n)e_{j}.$
(1.10)

Let $\overrightarrow{\mathfrak{3}}^{\nu}\in\mathbb{Z}^{\nu}$ be the vector
whose entries are ascending powers of three.

$\overrightarrow{\mathfrak{3}}^{\nu}=\sum_{j=1}^{\nu}3^{\nu-j}e_{j}.$ (1.11)

######  Example 4.

Let $\nu=5$.

$\overrightarrow{\mathfrak{3}}^{5}=\begin{bmatrix}3^{4}\\\ 3^{3}\\\ 3^{2}\\\
3^{1}\\\ 3^{0}\end{bmatrix}.$

Let $\mathcal{P}$ be the $\nu\times\nu$ permutation matrix characterized by
the following formula:

$\mathcal{P}=\sum_{j=1}^{\nu}e_{j,|j|_{\nu}+1},$ (1.12)

where $|j|_{\nu}$ denotes $j\mod\nu$. We define the $\nu\times\nu$ matrix
$\mathcal{L}_{n}$ associated to $n$ to be the diagonal matrix whose entries
are powers of two determined by the following formula:

$\mathcal{L}_{n}=\sum_{j=1}^{\nu}2^{m_{j}}e_{j,j}.$ (1.13)

We define the $\nu\times\nu$ matrix $\mathcal{D}_{n}$ associated to $n$ to be
the result of the matrix product of $\mathcal{L}_{n}$ and $\mathcal{P}$.

$\mathcal{D}_{n}=\mathcal{L}_{n}\times\mathcal{P}=\sum_{j=1}^{\nu}2^{m_{j}}e_{j,|j|_{\nu}+1}.$
(1.14)

We define the following $\nu\times\nu$ matrix associated to $n$, referred to
as $\mathcal{M}_{n}$, below:

$\mathcal{M}_{n}=\sum_{k=1}^{\nu}\mathcal{D}_{n}^{k-1}\sum_{j=1}^{\nu}e_{j,k}.$
(1.15)

Where $\mathcal{D}_{n}^{k}$ denote the $k$th power of $\mathcal{D}_{n}$ and
$\sum_{j=1}^{\nu}e_{j,k}$ denotes the matrix whose $k$th column is all ones
and is zero everywhere else.

######  Example 5.

Consider the integral loop induced by $n=85$ and $\gamma=47$. The matrix
$\mathcal{M}_{85}$ appears below,

$\mathcal{M}_{85}=\begin{bmatrix}1&2&8&16\\\ 1&4&8&64\\\ 1&2&16&32\\\
1&8&16&64\end{bmatrix}.$

######  Proposition 1.5.2.

Fix $\gamma\in\mathbb{Z}^{odd}_{>0}$, $n\in\mathbb{Z}^{odd}_{>0}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $[n]$ be the
associated integral loop vector of $n$. Let the matrix $\mathcal{M}_{n}$ be
given by Equation (1.15). Then $[n]$ and $\mathcal{M}_{n}$ satisfy the
following equality,

$[n]=\frac{\gamma}{2^{\rho}-3^{\nu}}\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}.$
(1.16)

Where $\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}$ denotes the product
of the $\nu\times\nu$ matrix $\mathcal{M}_{n}$ and the $\nu\times 1$ column
vector $\overrightarrow{\mathfrak{3}}^{\nu}$.

######  Example 6.

Again consider the integral loop induced by $n=85$ and $\gamma=47$. We verify
Equation (1.16),

$[85]=\begin{bmatrix}85\\\ 151\\\ 125\\\
211\end{bmatrix}=\frac{47}{47}\begin{bmatrix}1&2&8&16\\\ 1&4&8&64\\\
1&2&16&32\\\ 1&8&16&64\end{bmatrix}\begin{bmatrix}27\\\ 9\\\ 3\\\
1\end{bmatrix}=\frac{47}{2^{7}-3^{4}}\begin{bmatrix}1&2&8&16\\\ 1&4&8&64\\\
1&2&16&32\\\ 1&8&16&64\end{bmatrix}\begin{bmatrix}27\\\ 9\\\ 3\\\
1\end{bmatrix}.$

######  Proposition 1.5.3.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $[n]$ be the
associated integral loop vector of $n$. Let $\mathcal{M}_{n}$ be constructed
as by Equation (3.5). Let $(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence
associated to $n$. Let $s=\gcd(n,C_{\gamma}^{i_{1}}(n))$ and $p$ a prime
factor of $s$. Define $a,d\in\mathbb{Z}_{\geq 0}$ as the maximal exponents
such that $p^{a}$ divides every component of $[n]$ and $p^{d}$ divides every
component of $\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}$. Define
$b,c\in\mathbb{Z}_{\geq 0}$ as the maximal exponents so that $p^{b}$ divides
$\gamma$ and $p^{c}$ divides $(2^{\rho}-3^{\nu})$. Then $a,b,c,$ and $d$
satisfy the following equality:

$a-b+c-d=0.$

######  Theorem 1.5.4.

We will use the notation presented in Proposition 1.5.3. Furthermore assume
that $c>b-a$. Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and
$N\in\mathbb{Z}_{>0}$. Suppose further $n$ starts an integral loop of length
$N$. Let $B\in\\{0,1\\}^{**}$ such that $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$.
Let $\rho$ and $\nu$ be the count of the number of zeros and ones in a single
period of $B$. Let $[n]$ be the associated integral loop vector of $n$. Let
$\mathcal{M}_{n}$ be constructed as by Equation (3.5). Let $p$ be a prime
factor of $[n]$ of multiplicity $a>0$, then $\det(\mathcal{M}_{n})\equiv
0\pmod{p}$.

######  Example 7.

Consider the integral loop induced by $n=65$ and $\gamma=65455$. We find that
$\overrightarrow{\mathfrak{3}}^{4}$ is in the nullspace of
$\mathcal{M}_{65}\pmod{5,13}$.

$\begin{bmatrix}1&2&4&8\\\ 1&2&4&32768\\\ 1&2&16384&32768\\\
1&8192&16384&32768\end{bmatrix}\begin{bmatrix}27\\\ 9\\\ 3\\\
1\end{bmatrix}=\begin{bmatrix}65\\\ 32825\\\ 81965\\\
155675\end{bmatrix}\equiv\begin{bmatrix}0\\\ 0\\\ 0\\\
0\end{bmatrix}\pmod{5\text{ and }13}.$

Now consider the following integral loops, which we denote by $A$, $B$, $C$,
and $D$:

| $n$ | $\gamma$ |
---|---|---|---
$A$ | 65 | 65455 |  | $\\{65,65650,32825,163930,81965,311350,155675,$
---
$532480,266240,133120,66560,33280,16640,8320,$
$4160,2080,1040,520,260,130\\}$
$B$ | 13 | 13091 |  | $\\{13,13130,6565,32786,16393,62270,31135,106496,$
---
$53248,26624,13312,6656,3328,1664,832,416,$
$208,104,52,26\\}$
$C$ | 5 | 5035 |  | $\\{5,5050,2525,12610,6305,23950,11975,40960,20480,$
---
$10240,5120,2560,1280,640,320,160,80,40,20,10\\}$
$D$ | 1 | 1007 |  | $\\{1,1010,505,2522,1261,4790,2395,8192,4096,2048,$
---
$1024,512,256,128,64,32,16,8,4,2\\}$

We then find that the integral loop $B=A/5$, $C=A/13$, and $D=A/65=B/13=C/5$.

######  Remark.

A discussion of this example is presented in chapter three, section two.

######  Example 8.

Consider the integral loop induced by $n=7$ and $\gamma=7$. We find that
$\overrightarrow{\mathfrak{3}}^{2}$ is in the nullspace of
$\mathcal{M}_{7}\pmod{7}$.

$\mathcal{M}_{7}\overrightarrow{\mathfrak{3}}^{2}=\begin{bmatrix}1&4\\\
1&4\end{bmatrix}\begin{bmatrix}3\\\ 1\end{bmatrix}=\begin{bmatrix}7\\\
7\end{bmatrix}\equiv\begin{bmatrix}0\\\ 0\end{bmatrix}\pmod{7}.$

Consider the integral loop induced by $n=37$ and $\gamma=37$. We find that
$\overrightarrow{\mathfrak{3}}^{3}$ is in the nullspace of
$\mathcal{M}_{37}\pmod{37}$.

$\mathcal{M}_{37}\overrightarrow{\mathfrak{3}}^{3}=\begin{bmatrix}1&4&16\\\
1&4&16\\\ 1&4&16\end{bmatrix}\begin{bmatrix}9\\\ 3\\\
1\end{bmatrix}=\begin{bmatrix}37\\\ 37\\\
37\end{bmatrix}\equiv\begin{bmatrix}0\\\ 0\\\ 0\end{bmatrix}\pmod{37}.$

| n | $\gamma$ |
---|---|---|---
A | 7 | 7 | $\\{7,28,14\\}$
B | 37 | 37 | $\\{37,148,74\\}$
C | 1 | 1 | $\\{1,4,2\\}$

We then find that the integral loop $C=B/37=A/7$.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Let the quantities
$m_{j}$ be given by Proposition 1.5.1. Let $z_{1},...,z_{n}$ be defined by,

$z_{i}=2^{\frac{1}{\nu}\sum_{k=1}^{\nu-1}km_{|i+k-2|_{\nu}+1}}.$ (1.17)

Where $|i+k-2|_{\nu}$ is $i+k-2$ modulo $\nu$. Then we define the circulant
matrix $\mathcal{R}_{n}$ associated to $n$ as,

$\mathcal{R}_{n}=\mathcal{R}(z_{1},...,z_{n})=\sum_{j=1}^{\nu}z_{j}\mathcal{P}^{j-1}.$
(1.18)

######  Proposition 1.5.5.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Let $\mathcal{M}_{n}$
be constructed as by Equation (1.15). Let $\mathcal{R}_{n}$ be constructed by
Equation (1.18). Then the following equality is satisfied,

$\left|\det(\mathcal{M}_{n})\right|=\left|\det(\mathcal{R}_{n})\right|.$

######  Theorem 1.5.6.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Assume $\nu$ is prime.
Let the quantities $m_{j}$ from Proposition 1.5.1 satisfy Equation (1.17) so
that $z_{1},...,z_{\nu}$ are integers. Let $\mathcal{R}_{n}$ be constructed by
Equation (1.18). Let $p$ be a prime factor of $2^{\rho}-3^{\nu}$ distinct from
$\nu$ so that the residue class $p\pmod{\nu}$ generates the whole group
$\mathbb{Z}_{\nu}^{*}$. Then $p\nmid\det(\mathcal{M}_{n})$ if and only if
$p\nmid(z_{1}+...+z_{\nu})$ and for some $1\leq i<j\leq\nu$ we have
$z_{i}\not\equiv z_{j}\pmod{p}$.

######  Example 9.

Consider the integral loop induced by $n=373$ and $\gamma=1048333$. In this
case $m_{1}=4,m_{2}=2,m_{3}=2,m_{4}=4$ and $m_{5}=14$ such that
$2^{20}-3^{5}=1048333=11\times 13\times 7331$. We find that
$z_{1}=8,z_{2}=8192,z_{3}=2048,z_{4}=256$ and $z_{5}=32$. Thus
$\mathcal{R}_{373}$ has all integer coefficients. The prime factors 11 and
7331 are both in the residue class of 1, and cannot be used. However, the
residue class of 13 is 3, which indeed generates the whole group
$\mathbb{Z}_{5}^{*}$. We find that $8+8192+2048+256+32=10536\equiv
6\pmod{13}$. Furthermore $32\equiv 6\pmod{13}$ and $8\equiv 8\pmod{13}$. Thus
by the theorem we conclude that $\det(\mathcal{M}_{373})$ is nonsingular
modulo 13. Furthermore,
$\det(\mathcal{M}_{373})=36861972294903300096=\det(\mathcal{R}_{373})\equiv
6{\pmod{13}}$. Finally, $\det(\mathcal{M}_{373})\not\equiv
0{\pmod{2^{20}-3^{5}}}$.

###  1.6 A Note Regarding Chapters Two Through Four

The remainder of this thesis is organized into three chapters. Chapter two
presents the background material and essential notation for the remainder of
the thesis. Chapter three presents the matrix notation and various properties
used to express integral loop vectors. Chapter four is a muesli of ideas
related to chapter three.

##  Chapter 2 Fundamentals of Bounded Trajectories

###  2.1 Preliminary Definitions

######  Definition 2.1.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$. Let
$C_{\gamma}:\mathbb{Z}_{>0}\rightarrow\mathbb{Z}_{>0}$ be defined as,

$C_{\gamma}(n)=\begin{cases}3n+\gamma&\text{if }n\equiv 1\pmod{2},\\\
\frac{n}{2}&\text{if }n\equiv 0\pmod{2}.\end{cases}$ (2.1)

Let $C_{\gamma}^{0}(n)=n$. Furthermore, for $k\geq 0$, denote function
composition as $C_{\gamma}^{k+1}(n)=C_{\gamma}^{k}\circ C_{\gamma}(n)$.
Finally, if $\gamma=1$ then we write $C$ instead of $C_{1}$.

######  Definition 2.1.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$. Let
$\chi_{\gamma}:\mathbb{Z}_{>0}\rightarrow\\{0,1\\}$ be defined as,

$\chi_{\gamma}(n)=\begin{cases}1&\text{if }C_{\gamma}(n)\equiv 1\pmod{2},\\\
0&\text{if }C_{\gamma}(n)\equiv 0\pmod{2}.\end{cases}$ (2.2)

Let $\chi_{\gamma}^{0}(n)\equiv n\pmod{2}$. Furthermore, for $k\geq 0$, denote
function composition as $\chi_{\gamma}^{k+1}(n)=\chi_{\gamma}\circ
C_{\gamma}^{k+1}(n)$. Finally, if $\gamma=1$ then we write $\chi$ instead of
$\chi_{1}$.

######  Definition 2.1.3.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. Let
$\\{C_{\gamma}^{0}(n),C_{\gamma}^{1}(n),...\\}$ denote the trajectory of $n$.

######  Definition 2.1.4.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. Let
$\\{\chi_{\gamma}^{0}(n),\chi_{\gamma}^{1}(n),...\\}$ denote the
characteristic trajectory of $n$.

######  Example 10.

The first four terms of the trajectory and characteristic trajectory induced
by $n=5$ and $\gamma=1$ appears below respectively,

$\\{5,16,8,4\\}\text{ and }\\{1,0,0,0\\}.$

Let $\\{0,1\\}^{**}$ denote the set of binary sequences of infinite length.

######  Definition 2.1.5.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. We say
$B\in\\{0,1\\}^{**}$ is associated to the characteristic trajectory of $n$ if
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$.

######  Proposition 2.1.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}$, and
$N\in\mathbb{Z}_{>0}$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones, respectively in $B$ for all $i$ between zero and
$N-1$ inclusive.

  1. 1.

If n is odd, let $m_{1},...,m_{\nu-1}$ be the number of zeros between the
$(j-1)$th and $j$th one. Let $m_{0}=0$ and $m_{\nu}$ be the remaining zeros
after the last one.

  2. 2.

If n is even, let $m_{0}$ be the number of leading zeros. Observe that
$n=2^{m_{0}}\tilde{n}$ for $\tilde{n}$ being odd. So we obtain
$m_{1},...,m_{\nu-1}$ by (1) and $\tilde{n}$.

Then $n$ satisfies the following equality

$C_{\gamma}^{N}(n)=\frac{3^{\nu}n+\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}}.$
(2.3)

###### Proof.

Let us assume first that $n$ is odd, which implies that $m_{0}=0$. Therefore
Equation (2.3) reduces to the form,

$C_{\gamma}^{N-1}(n)=\frac{3^{\nu}n+\gamma(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}}.$

By construction of $\rho$ and $\nu$, we make the substitution $N-1=\rho+\nu$.
We know that $C_{\gamma}^{N-1}(n)$ represents $N-1$ compositions of the
$C_{\gamma}$ mapping with starting integer $n$. Therefore, we can advance the
trajectory of $n$ by one, and subtract one step from $N-1$ in the following
manner,

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho+\nu}(n)=C_{\gamma}^{\rho+\nu-1}\circ
C_{\gamma}(n)=C_{\gamma}^{\rho+\nu-1}(3n+\gamma).$

Both the terms $3n$ and $\gamma$ are odd. Therefore their sum is even. We can
divide by two, $m_{1}$ number of times yielding the following expression:

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho-m_{1}+\nu-1}\circ
C^{m_{1}}_{\gamma}(3n+\gamma)=C_{\gamma}^{\rho-
m_{1}+\nu-1}(\frac{3n+\gamma}{2^{m_{1}}}).$

By hypothesis, this expression is again odd. Therefore we can apply the
$C_{\gamma}$ map for one more step.

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho-m_{1}+\nu-2}\circ
C_{\gamma}(\frac{3n+\gamma}{2^{m_{1}}})=C_{\gamma}^{\rho-
m_{1}+\nu-2}(\frac{3^{2}n+3\gamma+2^{m_{1}}\gamma}{2^{m_{1}}}).$

In turn, this expression is again even. Therefore we can divide by $m_{2}$
powers of two. Following this, we can reduce the expression again,

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho-m_{1}-m_{2}+\nu-2}\circ
C^{m_{2}}_{\gamma}(\frac{3n+\gamma}{2^{m_{1}}})=C_{\gamma}^{\rho-
m_{1}-m_{2}+\nu-2}(\frac{3^{2}n+3\gamma+2^{m_{1}}\gamma}{2^{m_{1}+m_{2}}}).$

We proceed to follow this process inductively until the length of the entire
finite sub-sequence of $B$ is exhausted.

$\displaystyle C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho-
m_{1}-...-m_{\nu}+\nu-1-...-1}$ $\displaystyle\circ
C^{m_{\nu-1}}_{\gamma}(\frac{3^{\nu}n+3^{\nu-1}\gamma+3^{\nu-2}2^{m_{1}}\gamma+3^{\nu-3}2^{m_{1}+m_{2}}\gamma+...}{2^{m_{1}+m_{2}+...}}),$
$\displaystyle=C_{\gamma}^{0}(\frac{3^{\nu}n+3^{\nu-1}\gamma+3^{\nu-2}2^{m_{1}}\gamma+3^{\nu-3}2^{m_{1}+m_{2}}\gamma+...}{2^{\rho}}),$
$\displaystyle=\frac{3^{\nu}n+\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}}.$

On the other hand, suppose that $n$ is even. Then $m_{0}>0$, and by hypothesis
$n=2^{m_{0}}\tilde{n}$ for an odd integer $\tilde{n}$. Starting from Equation
(2.3) we find by taking $m_{0}$ steps,

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho+\nu}(n)=C_{\gamma}^{\rho-m_{0}+\nu}\circ
C^{m_{0}}_{\gamma}(n)=C_{\gamma}^{\rho-m_{0}+\nu}(\frac{n}{2^{m_{0}}}).$

Recall by hypothesis $n=2^{m_{0}}\tilde{n}$ implies
$\frac{n}{2^{m_{0}}}=\tilde{n}$. Substituting this quantity in yields:

$C_{\gamma}^{N-1}(n)=C_{\gamma}^{\rho-
m_{0}+\nu}(\frac{n}{2^{m_{0}}})=C_{\gamma}^{\rho-m_{0}+\nu}(\tilde{n}).$

We then consider the previous argument starting with $\tilde{n}$,
$\tilde{\rho}=\rho-m_{0}$, and $\nu$ unchanged.

$\displaystyle C_{\gamma}^{N-1-m_{0}}(\tilde{n})$
$\displaystyle=\frac{3^{\nu}\tilde{n}+\gamma(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\tilde{\rho}}},$
$\displaystyle=\frac{3^{\nu}\frac{n}{2^{m_{0}}}+\gamma(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho-
m_{0}}},$
$\displaystyle=\Big{(}\frac{2^{m_{0}}}{2^{m_{0}}}\Big{)}\frac{3^{\nu}\frac{n}{2^{m_{0}}}+\gamma(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho-
m_{0}}},$ $\displaystyle=\frac{3^{\nu}n+\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}}.$

Therefore we find that,

$C^{N-1}_{\gamma}(n)=C^{N-1-m_{0}}_{\gamma}(\tilde{n})=\frac{3^{\nu}n+\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}}.$

∎

######  Example 11.

Consider the first nine terms of the characteristic trajectory induced by
$n=19$ an $\gamma=1$ below,

$\\{1,0,1,0,0,0,1,0,1\\}.$

We verify Equation (2.3) for $C^{9}(19)$.

$\displaystyle C^{9}(19)$ $\displaystyle=\frac{3^{4}\times
19+2^{0}(3^{3}+3^{2}\times 2^{1}+3^{1}\times 2^{1+3}+3^{0}\times
2^{1+3+1})}{2^{5}},$ $\displaystyle=\frac{1539+27+18+48+32}{32},$
$\displaystyle=\frac{1664}{32}=52.$

######  Definition 2.1.6.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. If there
exists a $N\in\mathbb{Z}_{>0}$ so that $C_{\gamma}^{N}(n)=n$ then we say $n$
starts an integral loop.

######  Definition 2.1.7.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. Suppose $n$
starts an integral loop. Let
$N=\min(\\{i\in\mathbb{Z}_{>0}|C_{\gamma}^{i}(n)=n\\})$ be the least positive
integer so that $C_{\gamma}^{N}(n)=n$. Then we say $n$ starts an integral loop
of length $N$.

######  Example 12.

The integral loop induced by $n=23$ and $\gamma=37$ appears below,

$\\{23,106,53,196,98,49,184,92,46\\}.$

Suppose $n$ starts an integral loop of length $N$. Then the binary sequence
$B$ associated to $n$ has a repeating period of length $N$. Let $\rho$ be the
number of zeros in a single period of $B$. Let $\nu$ be the number of ones in
a single period of $B$. Let $m_{j}$ denote the number of zeros between the
$(j-1)$th and the $j$th one. Let $m_{\nu}$ representing the remaining zeros
after the last one. Note that $\sum_{j}m_{j}=\rho$.

######  Proposition 2.1.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$ and $n\in\mathbb{Z}_{>0}$. Let
$B\in\\{0,1\\}^{**}$ such that $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Suppose
that $N$ is the smallest positive integer such that $C_{\gamma}^{N+1}(n)=n$.
Let $\rho$ and $\nu$ be the count of the number of zeros and ones,
respectively, in $B$ for all $i$ between $0$ and $N$ inclusive.

  1. 1.

If n is odd, let $m_{1},...,m_{v-1}$ be the number of zeros between the
$(j-1)$th and $j$th one. Let $m_{0}=0$ and $m_{\nu}$ be the remaining zeros
after the last one.

  2. 2.

If n is even, let $m_{0}$ be the number of leading zeros. Observe that
$n=2^{m_{0}}\tilde{n}$ for $\tilde{n}$ being odd. So we obtain
$m_{1},...,m_{\nu-1}$ by (1) and $\tilde{n}$.

Then $n$ satisfies the following equality

$n=\frac{\gamma
2^{m_{0}}(3^{\nu-1}+\sum_{r=1}^{\nu-1}3^{\nu-1-r}2^{\sum_{j=1}^{r}m_{j}})}{2^{\rho}-3^{\nu}}.$
(2.4)

###### Proof.

Equation (2.4) can be derived from Equation (2.3) by setting
$C_{\gamma}^{N}(n)=n$. ∎

We will refer to Equation (2.4) as the Integral Loop Formula.

######  Example 13.

Consider again the integral loop induced by $n=23$ and $\gamma=37$. With
respect to Equation (2.4) we find that,

$\displaystyle n$ $\displaystyle=\frac{37(3^{3-1}+3^{3-2}\times
2^{1}+3^{3-3}\times 2^{1+2})}{2^{6}-3^{3}},$ $\displaystyle=\frac{37(9+3\times
2+1\times 8)}{37}=23.$

######  Definition 2.1.8.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$. The trajectory of an integer
$n\in\mathbb{Z}_{>0}$ is said to be bounded if there exists some
$\Omega\in\mathbb{Z}_{>0}$ such that
$\sup\limits_{i>0}(\\{C^{i}_{\gamma}(n)\\})<\Omega$.

With these precursory definitions established, we will proceed to study the
properties of bounded trajectories.

###  2.2  The Integral Loop Vector

######  Definition 2.2.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $i_{j}$ be the
subindexing of $i$ so that for all $0\leq j\leq\nu-1$ we have
$\chi_{\gamma}^{i_{j}}(n)\equiv 1\pmod{2}$. Note also $i_{0}=0$. We call
$(i_{j})_{j=0}^{\nu-1}$ the indexing sequence associated to $n$.

######  Definition 2.2.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence associated to $n$. Let
$e_{j}$ denote the standard basis of $\mathbb{R}^{\nu}$. We call $[n]$ the
integral loop vector expressed in Equation (2.5):

$[n]=\begin{bmatrix}C_{\gamma}^{i_{0}}(n)\\\ C_{\gamma}^{i_{1}}(n)\\\
\vdots\\\
C_{\gamma}^{i_{\nu-1}}(n)\end{bmatrix}=\sum_{j=1}^{\nu}C_{\gamma}^{i_{j-1}}(n)e_{j}.$
(2.5)

######  Example 14.

Consider the integral loop induced by $n=421$ and $\gamma=13$. With respect to
Equation (2.5), we write the integral loop vector [421] as follows:

$[421]=\begin{bmatrix}421\\\ 319\\\ 485\\\ 367\\\ 557\end{bmatrix}.$

######  Proposition 2.2.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the index sequence associated to $n$. Then the
quantities of $m_{j}$ from Proposition 2.1.2 and $i_{j}$ from Definition 2.2.1
can be related by the following equations:

$\begin{cases}m_{j}&=i_{j}-i_{j-1}-1,\text{ if }1\leq j\leq\nu-1,\\\
m_{\nu}&=N-1-i_{\nu-1}.\end{cases}$ (2.6)

###### Proof.

For $1\leq j\leq\nu-1$ the statement follows directly from construction. That
leaves only the last term to check. We observe that by taking the sum of all
terms, we have a telescoping sum:

$\displaystyle m_{1}+...+m_{\nu-1}+m_{\nu}$
$\displaystyle=i_{1}-i_{0}-1+i_{2}-i_{1}-1+...+i_{\nu-1}-i_{\nu-2}-1+N-i_{\nu-1}-1,$
$\displaystyle=N-i_{0}-\nu=\rho+\nu-0-\nu=\rho.$

Thus we see the last term necessarily counts the remaining number of even
numbers before the period repeats. ∎

Observe that for $j\geq 1$, we have $[n]_{j}=C_{\gamma}^{i_{j-1}}(n)$. This
highlights the relationship between the subindex $j$ and the indexing sequence
$(i_{j})$. This naturally extends to an infinite dimensional array. However,
in the case of integral loops, we consider only the first period, which has
dimension $\nu$.

######  Definition 2.2.3.

Fix $\gamma,n,\tilde{n}\in\mathbb{Z}_{>0}^{odd}$, and $N\in\mathbb{Z}_{>0}$.
Suppose both $n$ and $\tilde{n}$ start integral loops of length $N$. Let
$B,\tilde{B}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$ and $\tilde{n}$, respectfully. Let
$\rho,\tilde{\rho},\nu\text{ and }\tilde{\nu}$ be the count for the number of
zeros and ones in a single period of $B$ and $\tilde{B}$, respectfully.
Suppose further that $\nu=\tilde{\nu}$. Let $[n]$ and $[\tilde{n}]$ be the
associated integral loop vectors. We state the following:

  1. 1.

If for all $j$, $[n]_{j}=[\tilde{n}]_{j}$ we say that $[n]$ and $[\tilde{n}]$
are equal and write $[n]=[\tilde{n}]$.

  2. 2.

If there exists a $0<k\leq\nu-1$, so that for all $j$,
$[n]_{j+k}=[\tilde{n}]_{j}$, we say that $[n]$ and $[\tilde{n}]$ are similar
and write $[n]\approx[\tilde{n}]$.

  3. 3.

If integral loop vectors $[n]$ and $[\tilde{n}]$ are neither equal or similar,
then we say they are distinct.

######  Example 15.

Consider the integral loop induced by $n=133$ and $\gamma=943$. The integral
loop vector associated to $133$ appears as:

$[133]=\begin{bmatrix}133\\\ 671\\\ 739\\\ 395\end{bmatrix}.$

Furthermore, we find that $[133]\approx[671]\approx[739]\approx[395]$. All
other integral loop vectors are distinct.

##  Chapter 3 Matrix Constructions Associated to Integral Loops

###  3.1 Construction of Matrix $\mathcal{D}_{n}$

Let $e_{j,k}$ ($1\leq j,k\leq\nu$) denote the standard basis of
$\mathbb{R}^{\nu\times\nu}$.

######  Definition 3.1.1.

Fix $\nu\in\mathbb{Z}_{>0}$. Let $\mathcal{P}$ be the $\nu\times\nu$
permutation matrix characterized by the following formula:

$\mathcal{P}=\sum_{j=1}^{\nu}e_{j,|j|_{\nu}+1},$ (3.1)

where $|j|_{\nu}$ denotes $j$ modulo $\nu$.

######  Example 16.

Let $\nu=5$.

$\mathcal{P}=\begin{bmatrix}0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\\\ 1&0&0&0&0\end{bmatrix}.$

######  Definition 3.1.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let the quantities $m_{j}$
be given by by Proposition 2.1.2. We define the $\nu\times\nu$ matrix
$\mathcal{L}_{n}$ associated to $n$ as follows:

$\mathcal{L}_{n}=\sum_{j=1}^{\nu}2^{m_{j}}e_{j,j}.$ (3.2)

######  Definition 3.1.3.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let the quantities $m_{j}$
be given by Proposition 2.1.2. We define the $\nu\times\nu$ matrix
$\mathcal{D}_{n}$ associated to $n$ to be the result of the matrix product of
$\mathcal{L}_{n}$ and $\mathcal{P}$:

$\mathcal{D}_{n}=\mathcal{L}_{n}\times\mathcal{P}=\sum_{j=1}^{\nu}2^{m_{j}}e_{j,|j|_{\nu}+1}.$
(3.3)

Where $|j|_{\nu}$ denotes $j$ modulo $\nu$.

######  Remark.

The matrix constructed above in Definition 3.1.3 is a close cousin to the
circulant matrix [7]. The distinction being that the rows of a circulant
matrix, apart from a right-shifting, are identical. In our case, we encoded
the finite binary sequence associated to the integral loop into the off-
diagonal elements.

######  Example 17.

Consider the integral loop induced by $n=19$ and $\gamma=37$. Then the matrix
$\mathcal{D}_{19}$ appears in the following form:

$\mathcal{D}_{19}=\begin{bmatrix}0&2&0\\\ 0&0&2\\\ 16&0&0\end{bmatrix}.$

######  Proposition 3.1.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let the quantities $m_{j}$
be given by Proposition 2.1.2 and the matrix $\mathcal{D}_{n}$ given by
Equation (3.3). Finally, let $k\in\mathbb{Z}_{>0}$ be given. Then the matrix
$\mathcal{D}_{n}$ has the following exponent rule:

$\mathcal{D}_{n}^{k}=\sum_{j=1}^{\nu}\left(2^{\sum_{r=0}^{k-1}m_{|j+r-1|_{\nu}+1}}\right)e_{j,|j+k-1|_{\nu}+1}.$

In particular, this implies $\mathcal{D}_{n}^{\nu}$ =
$2^{\rho}\mathbb{I}_{\nu}$, where $\mathbb{I}_{\nu}$ is the $\nu\times\nu$
identity matrix.

###### Proof.

Observe first that if $k=1$ we arrive back to Equation (3.3). Suppose then the
exponent rule holds up to some quantity $k^{*}$. Then for $k^{*}+1$ we have:

$\displaystyle\mathcal{D}_{n}^{k^{*}+1}$
$\displaystyle=\mathcal{D}_{n}^{k^{*}}\times\mathcal{D}_{n},$
$\displaystyle=\mathcal{D}_{n}^{k^{*}}\times\mathcal{L}_{n}\times\mathcal{P}.$

Recall that $\mathcal{L}_{n}$ is a diagonal matrix, so the matrix product
simply adds the respective $m_{j}$ to the end of summand in the exponents for
each entry of $\mathcal{D}_{n}^{k^{*}}$. Similarly, the matrix $\mathcal{P}$
is a permutation matrix that right-shifts all entries by one element. In this
way we arrive at the desired form. Finally, we see that when the matrix
$D_{n}$ is taken to the $\nu$ power, that every diagonal element is exactly
$\sum_{j}m_{j}=\rho$. ∎

######  Example 18.

Consider the integral loop induced by $n=23$ and $\gamma=37$. The first three
powers of $\mathcal{D}_{23}$ appear as follows:

$\begin{matrix}\mathcal{D}_{23}^{1}=\begin{bmatrix}0&2&0\\\ 0&0&4\\\
8&0&0\end{bmatrix},&\mathcal{D}_{23}^{2}=\begin{bmatrix}0&0&8\\\ 32&0&0\\\
0&16&0\end{bmatrix},&\mathcal{D}_{23}^{3}=\begin{bmatrix}64&0&0\\\ 0&64&0\\\
0&0&64\end{bmatrix}.\end{matrix}$

###  3.2 Construction of Matrix $\mathcal{M}_{n}$

####  3.2.1 Preliminary Notation

######  Definition 3.2.1.

Fix $\nu\in\mathbb{Z}_{>0}$. Let $\overrightarrow{\mathfrak{3}}^{\nu}$ be the
$\nu$-column vector whose entries are the ascending powers of three, appearing
as follows:

$\overrightarrow{\mathfrak{3}}^{\nu}=\sum_{j=1}^{\nu}3^{\nu-j}e_{j}.$ (3.4)

######  Example 19.

Let $\nu=5$.

$\overrightarrow{\mathfrak{3}}^{5}=\begin{bmatrix}3^{4}\\\ 3^{3}\\\ 3^{2}\\\
3^{1}\\\ 3^{0}\end{bmatrix}.$

######  Definition 3.2.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let the matrix
$\mathcal{D}_{n}$ be given by Equation (3.3). We define the following
$\nu\times\nu$ matrix $\mathcal{M}_{n}$ below:

$\mathcal{M}_{n}=\sum_{k=1}^{\nu}\mathcal{D}_{n}^{k-1}\sum_{j=1}^{\nu}e_{j,k}.$
(3.5)

Where $\mathcal{D}^{k}_{n}$ denotes the $k$th power of $\mathcal{D}_{n}$ and
$\sum_{j=1}^{\nu}e_{j,k}$ denotes the matrix whose $k$th column is all ones
and is zero everywhere else.

######  Example 20.

Consider the integral loop induced by $n=65$ and $\gamma=943$. Then the matrix
$\mathcal{M}_{65}$ appears as follows:

$\mathcal{M}_{65}=\begin{bmatrix}1&2&4&8\\\ 1&2&4&512\\\ 1&2&256&512\\\
1&128&256&512\end{bmatrix}.$

######  Proposition 3.2.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $[n]$ be the
associated integral loop vector of $n$. Let the matrix $\mathcal{M}_{n}$ be
given by Equation (3.5). Then $[n]$ and $\mathcal{M}_{n}$ satisfy the
following equality,

$[n]=\frac{\gamma}{2^{\rho}-3^{\nu}}\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}.$
(3.6)

Where $\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}$ denotes the product
of the $\nu\times\nu$ matrix $\mathcal{M}_{n}$ and the $\nu\times 1$ column
vector $\overrightarrow{\mathfrak{3}}^{\nu}$.

###### Proof.

This follows directly from Proposition 2.1.2. ∎

######  Example 21.

Consider the integral loop induced by $n=23$ and $\gamma=37$. We verify
Proposition 3.2.1 as follows:

$[23]=\begin{bmatrix}23\\\ 53\\\
49\end{bmatrix}=\frac{37}{37}\begin{bmatrix}1&2&8\\\ 1&4&32\\\
1&8&16\end{bmatrix}\begin{bmatrix}9\\\ 3\\\
1\end{bmatrix}=\frac{37}{2^{6}-3^{3}}\begin{bmatrix}1&2&8\\\ 1&4&32\\\
1&8&16\end{bmatrix}\begin{bmatrix}9\\\ 3\\\ 1\end{bmatrix}.$

####  3.2.2 Elementary Properties of Integral Loops

######  Lemma 3.2.2.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence associated to $n$. Let $p>2$
be a prime. If $p$ divides two of $C_{\gamma}^{i_{j}}(n)$,
$C_{\gamma}^{i_{j+1}}(n)$, or $\gamma$ then $p$ divides the third quantity as
well.

###### Proof.

Suppose first that $p$ divides $C_{\gamma}^{i_{j}}(n)$ and $\gamma$.

$\displaystyle C\circ C_{\gamma}^{i_{j}}(n)=3C_{\gamma}^{i_{j}}(n)+\gamma$
$\displaystyle=2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n),$ $\displaystyle
p\left(\frac{3C_{\gamma}^{i_{j}}(n)+\gamma}{p}\right)$
$\displaystyle=2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n).$

It is an elementary result in number theory that $C_{\gamma}^{i_{j+1}}(n)$
must have $p$ as a prime factor. Now suppose $p$ divides
$C_{\gamma}^{i_{j+1}}(n)$ and $\gamma$.

$\displaystyle 2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n)$
$\displaystyle=3C_{\gamma}^{i_{j}}(n)+\gamma,$ $\displaystyle
p\left(\frac{2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n)-\gamma}{p}\right)$
$\displaystyle=3C_{\gamma}^{i_{j}}(n).$

$C_{\gamma}^{i_{j}}(n)$ must have $p$ as a prime factor. Finally suppose that
$p$ divides $C_{\gamma}^{i_{j}}(n)$ and $C_{\gamma}^{i_{j+1}}(n)$.

$\displaystyle C\circ C_{\gamma}^{i_{j}}(n)$
$\displaystyle=3C_{\gamma}^{i_{j}}(n)+\gamma=2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n),$
$\displaystyle\gamma$
$\displaystyle=p\left(\frac{2^{m_{j+1}}C_{\gamma}^{i_{j+1}}(n)-3C_{\gamma}^{i_{j}}(n)}{p}\right).$

Thus $\gamma$ must have $p$ as a prime factor. As we have tested all three
possibilities, we conclude that if $p$ divides two of $C_{\gamma}^{i_{j}}$,
$C_{\gamma}^{i_{j+1}}(n)$, or $\gamma$ then $p$ divides the third quantity as
well. ∎

######  Lemma 3.2.3.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence associated to $n$. Let $p>2$
be a prime. If $p$ divides only one of $C_{\gamma}^{i_{j}}(n)$, or $\gamma$
then $p$ cannot divide $C_{\gamma}^{i_{j+1}}(n)$.

###### Proof.

This follows directly from Lemma 3.2.2. ∎

######  Example 22.

Consider the integral loop induced by $n=629$ and $\gamma=5^{4}=625$. This
integral loop is of length $N=144$ with $\nu=43$ odd positive integers. None
of which are a multiple of five.

######  Lemma 3.2.4.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$ in the $3x+\gamma$ Problem. Let
$s=\gcd(n,\gamma)$ and let $p$ be a prime factor of $s$. Then $n/p$ starts an
integral loop of length $N$ in the $3x+\gamma/p$ Problem.

###### Proof.

Let $A$ be the trajectory of $n$ and $B$ be the trajectory of $n^{\prime}$.

$\displaystyle A$
$\displaystyle=\\{C_{\gamma}^{0}(n),C_{\gamma}^{1}(n),...,C_{\gamma}^{N-1}(n),C_{\gamma}^{N}(n),...\\},$
$\displaystyle=\\{n,3n+\gamma,...,2n,n,...\\},$
$\displaystyle=\\{p\frac{n}{p},3p\frac{n}{p}+p\frac{\gamma}{p},...,2\frac{n}{p},p\frac{n}{p},...\\},$
$\displaystyle=p\\{\frac{n}{p},3\frac{n}{p}+\frac{\gamma}{p},...,2\frac{n}{p},\frac{n}{p},...\\},$
$\displaystyle=p\\{C_{\frac{\gamma}{p}}^{0}(\frac{n}{p}),C_{\frac{\gamma}{p}}^{1}(\frac{n}{p}),...,C_{\frac{\gamma}{p}}^{N-1}(\frac{n}{p}),C_{\frac{\gamma}{p}}^{N}(\frac{n}{p}),...\\},$
$\displaystyle=pB.$

We find that the trajectory starting at $n/p$ has a period of length $N$, e.g.
$C_{\frac{\gamma}{p}}^{N}(\frac{n}{p})=\frac{n}{p}$. Thus, by definition $n/p$
starts an integral loop of length N in the $3x+\gamma/p$ Problem. ∎

######  Remark.

We have shown that if the starting integer $n$ and the additive constant
$\gamma$ both share a prime factor $p$, then we can divide by $p$, and create
a new integral loop.

######  Lemma 3.2.5.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence associated to $n$. Let
$s=gcd(C_{\gamma}^{i_{0}}(n),...,C_{\gamma}^{i_{\nu}}(n))$, and let $s$ have
prime factors $p_{1},...,p_{k}$ Define $a_{1},...,a_{k}\in\mathbb{Z}_{\geq 0}$
as the maximal exponents so that $p_{j}^{a_{j}}$ divides each component of
$[n]$. Then the number of integral loops that can be constructed by removing
prime factors from the trajectory of $n$ is expressed by the following
formula,

$\prod_{j=1}^{k}(1+a_{j}).$

###### Proof.

This is a very classic problem in combinatorics where one chooses $k$ objects
from a set of $n$ objects with repeated elements. ∎

######  Lemma 3.2.6.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let
$(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence associated to $n$. Let
$s_{j}=\gcd(C_{\gamma}^{i_{j}}(n),C_{\gamma}^{i_{j+1}}(n))$ for all $0\leq
j\leq\nu-1$. Let $0\leq j^{\prime}\leq\nu-1$ be fixed. If $p$ is a prime
factor of $s_{j^{\prime}}$ of multiplicity $k>0$, then it is a prime factor
for all $s_{j}$ of multiplicity $k$.

###### Proof.

Recall from Lemma 3.2.2 that if $C_{\gamma}^{i_{j^{\prime}}}(n)$ and
$C_{\gamma}^{i_{j^{\prime}+1}}(n)$ both have a prime factor $p$, then $\gamma$
must also have the same prime factor. Again as a consequence of Lemma 3.2.2 we
conclude that for all $0\leq j\leq\nu-1$, $C_{\gamma}^{i_{j}}(n)$ has prime
factor $p$. By Lemma 3.2.4 we may divide the integral loop starting with
$C_{\gamma}^{i_{j^{\prime}}}(n)$ by $p$, yielding a new integral loop. If the
multiplicity of $p$ is one, then we are done. Else, we reapply Lemma 3.2.2 to
show $\gamma$ has another factor of $p$. Again by Lemma 3.2.2 we find that for
all $0\leq j\leq\nu-1$, $C_{\gamma}^{i_{j}}(n)$ has another copy of $p$. We
then apply Lemma 3.2.4 to divide the integral loop by another copy of $p$. We
proceed inductively until all $k$ copies of $p$ have been exhausted.

Suppose there exists another $0\leq j^{\prime\prime}\leq\nu-1$ such that
$s_{j^{\prime\prime}}$ has prime factor $p$ but with multiplicity
$k^{\prime\prime}>k$. By the preceding argument we would have been able to
divide $C_{\gamma}^{i_{j^{\prime}}}(n)$ and $C_{\gamma}^{i_{j^{\prime}+1}}(n)$
by another factor of $p$. However, we had already assumed that
$s_{j^{\prime}}$ had only $k$ copies of $p$. This is a contradiction. As
$s_{j^{\prime}}$ was arbitrary, we conclude that if $p$ is a prime factor of
$s_{j^{\prime}}$ of multiplicity $k>0$ then it is a prime factor for all
$s_{j}$ of multiplicity $k$. ∎

######  Lemma 3.2.7.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $s=\gcd(n,C_{\gamma}^{1}(n),\gamma)$
and $p$ a prime factor of $s$. Define $a,\tilde{a},b\in\mathbb{Z}_{\geq 0}$ as
the maximal exponents such that $p^{a}$ divides $n$, $p^{\tilde{a}}$ divides
$C_{\gamma}^{1}(n)$, and $p^{b}$ divides $\gamma$. Then
$b\geq\min(a,\tilde{a})$.

###### Proof.

Suppose $b<\min(a,\tilde{a})$. Then we may apply Lemma 3.2.4 to remove $b$
copies of $p$ from the integral loop. Then we may apply Lemma 3.2.2 forcing
$\gamma$ to have another factor of $p$. This is a contradiction. Therefore
$b\geq\min(a,\tilde{a})$. ∎

######  Proposition 3.2.8.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Let $n$
start an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $[n]$ be the
associated integral loop vector of $n$. Let $\mathcal{M}_{n}$ be constructed
as by Equation (3.5). Let $(i_{j})_{j=0}^{\nu-1}$ be the indexing sequence
associated to $n$. Let $s=\gcd(n,C_{\gamma}^{i_{1}}(n))$ and $p$ a prime
factor of $s$. Define $a,d\in\mathbb{Z}_{\geq 0}$ as the maximal exponents
such that $p^{a}$ divides every component of $[n]$ and $p^{d}$ divides every
component of $\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}$. Define
$b,c\in\mathbb{Z}_{\geq 0}$ as the maximal exponents so that $p^{b}$ divides
$\gamma$ and $p^{c}$ divides $(2^{\rho}-3^{\nu})$. Then $a,b,c,$ and $d$
satisfy the following equality:

$a-b+c-d=0.$

###### Proof.

This follows from Proposition 3.2.1. ∎

######  Remark.

Recall from Lemma 3.2.7 that $b\geq a$. Since $d>0$ this implies $c\geq b-a$.

####  3.2.3 Theorem Regarding Determinant of $\mathcal{M}_{n}$

######  Theorem 3.2.9.

We will use the notation presented in Proposition 3.2.8. Furthermore assume
that $c>b-a$. Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and
$N\in\mathbb{Z}_{>0}$. Suppose further $n$ starts an integral loop of length
$N$. Let $B\in\\{0,1\\}^{**}$ such that $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$.
Let $\rho$ and $\nu$ be the count of the number of zeros and ones in a single
period of $B$. Let $[n]$ be the associated integral loop vector of $n$. Let
$\mathcal{M}_{n}$ be constructed as by Equation (3.5). Let $p$ be a prime
factor of $[n]$ of multiplicity $a>0$, then $\det(\mathcal{M}_{n})\equiv
0\pmod{p}$.

###### Proof.

Recall Equation (3.6) and Equation (2.4). We find that,

$\displaystyle{}[n]$
$\displaystyle=\frac{\gamma}{2^{\rho}-3^{\nu}}\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu},$
$\displaystyle p^{a}\times\left(\frac{[n]}{p^{a}}\right)$
$\displaystyle=p^{b-c}\times\frac{\gamma
p^{c}}{(2^{\rho}-3^{\nu})p^{b}}\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu},$
$\displaystyle\left(\frac{p^{a}\times
p^{c}\frac{(2^{\rho}-3^{\nu})}{p^{c}}}{p^{b}\frac{\gamma}{p^{b}}}\right)\left(\frac{[n]}{p^{a}}\right)$
$\displaystyle=\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu},$
$\displaystyle p^{c-(b-a)}\times\left(\frac{(2^{\rho}-3^{\nu})p^{b}}{\gamma
p^{c}}\right)\times\left(\frac{[n]}{p^{a}}\right)$
$\displaystyle=\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}.$

On the left hand side, we have a product of three terms. By hypothesis
$c>b-a$, so the first term is a positive power of prime factor $p$. The
remaining two terms have no factor of $p$. The quotient
$[n]/p^{a}\in\mathbb{Z}^{\nu}$. Thus the left hand side is a vector integer
multiple of $p$. Therefore we have,

$\overrightarrow{0}\equiv\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}\pmod{p}.$

As the vector $\overrightarrow{\mathfrak{3}}^{\nu}$ is descending powers of
three, we can infer that $\overrightarrow{\mathfrak{3}}^{\nu}$ is not the zero
vector. Thus the null space of $\mathcal{M}_{n}$ modulo $p$ is at least one
dimensional. By the Rank-Nullity Theorem, we conclude that $\mathcal{M}_{n}$
is not full rank, and $\det(\mathcal{M}_{n})\equiv 0\pmod{p}$.

∎

######  Example 23.

Consider the integral loop induced by $n=18611$ and $\gamma=3367$. We find
that $\rho=12$ and $\nu=6$. With respect to the prime 37, we have $a=b=c=1$.
Finally $\det(\mathcal{M}_{18611})=-1910471786496\equiv 0{\pmod{37}}$.

######  Remark.

In Theorem 3.2.9, we require that $c>b-a$. This is a necessary requirement.
Consider the case $c=b-a$. If $a=0$ then the prime factor $p$ cannot divide
$[n]$ and we are done. On the other hand, consider the integral loop induced
by $n=5$ and $\gamma=5^{4}$. In this case $\rho=7$ and $\nu=1$. Thus
$2^{7}-3^{1}=125=5^{3}$. We find that $3=4-1$ but $\det(M_{n})=1\not\equiv
0\pmod{5}$.

######  Proposition 3.2.10.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{\geq 0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$
such that $B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the
count of the number of zeros and ones in a single period of $B$. Let $[n]$ be
the associated integral loop vector of $n$. Let $\mathcal{M}_{n}$ be
constructed as by Equation (3.5) and suppose it is invertible over
$\mathbb{C}$. If $\gamma|(2^{\rho}-3^{\nu})$, then $\det(\mathcal{M}_{n})$
contains all the prime factors of $[n]$.

###### Proof.

Since $\gamma|(2^{\rho}-3^{\nu})$,
$\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}=[n]\frac{2^{\rho}-3^{\nu}}{\gamma}\equiv\overrightarrow{0}\pmod{p}$
for each $p$ that divides all the terms of $[n]$. Hence
$\det(\mathcal{M}_{n})\equiv 0\pmod{p}$. ∎

######  Example 24.

Consider the integral loop induced by $n=3403$ and $\gamma=4193575$. In this
case $(2^{\rho}-3^{\nu})/\gamma=1$. We find that 83 is a prime factor for all
components of $[3403]$. Finally
$\det(\mathcal{M}_{3403}=1198591822881410672230400\equiv 0{\pmod{83}}$.

######  Example 25.

Consider the integral loop induced by $n=133$ and $\gamma=175$. We find that
$\overrightarrow{\mathfrak{3}}^{4}$ is in the null space of
$\mathcal{M}_{133}\pmod{7}$,

$\begin{bmatrix}1&2&8&64\\\ 1&4&32&128\\\ 1&8&32&64\\\
1&4&8&32\end{bmatrix}\begin{bmatrix}27\\\ 9\\\ 3\\\
1\end{bmatrix}=\begin{bmatrix}133\\\ 287\\\ 259\\\
119\end{bmatrix}\equiv\begin{bmatrix}0\\\ 0\\\ 0\\\ 0\end{bmatrix}\pmod{7}.$

Now consider the integral loops denoted by $A$ and $B$:

| $n$ | $\gamma$ |
---|---|---|---
A | 133 | 175 |  | $\\{133,574,287,1036,518,259,952,476,238,119,532,266\\}$
---
B | 19 | 25 |  | $\\{19,82,41,148,74,37,136,68,34,17,76,38\\}$
---

We find that the integral loop $B=A/7$.

######  Remark.

We will discuss the method to arrive at Examples (7) and (25). We begin with
Example (7). The finite binary sequence $B=10101010000000000000$ has four ones
and sixteen zeros. This allows us to implement the following trick regarding
differences in squares. Let $a,b\in\mathbb{Z}_{>0}$, then
$a^{2}-b^{2}=(a-b)(a+b)$. In our case we are allowed to do this twice:
$2^{16}-3^{4}=(2^{4}-3)(2^{4}+3)(2^{8}+9)=13\times 19\times 265$. Now fix
$m\in\mathbb{Z}_{\geq 0}$. We have the following identity regarding the
shuffling of integer powers $a$ and $b$:

$\frac{a^{m}-b^{m}}{a-b}=\sum_{i=0}^{m-1}a^{m-1-i}b^{i}.$

In our case $a=3$, $b=2$, and $m=\nu$. Thus, the denominator on the left hand
side vanishes. This yields the following:

$3^{\nu}-2^{\nu}=\sum_{i=0}^{\nu-1}3^{\nu-1-i}2^{i}.$

Compare the above to our finite binary sequence $B$ and the Integral Loop
Formula. We would find that the sums both match.

The last trick is strictly in number theory. The integer sequence
$(3^{i}-2^{i})_{i\geq 0}$ has a repeating pattern modulo five and thirteen.
The former appears as $\\{0,1,0,4,0,1,0,4,0,...\\}$. That is to say if
$i\equiv 0\pmod{2}$ then $3^{i}-2^{i}\equiv 0\pmod{5}$. The latter appears as
$\\{0,1,5,6,0,3,2,5,0,9,6,2,0,...\\}$. That is to say if $i\equiv 0\pmod{4}$
then $3^{i}-2^{i}\equiv 0\pmod{13}$. We conclude that if $i\equiv 0\pmod{4}$,
then $3^{i}-2^{i}$ is both a multiple of five and thirteen. Thus our starting
integer $n$ and the quantity $2^{16}-3^{4}$ both have two prime factors in
common.

As for Example (25), the construct is largely the same. The finite binary
sequence $B=101001000100$ has four ones and eight zeros. We apply the same
difference of squares to find $2^{8}-3^{4}=(2^{2}-3)(2^{2}+3)(2^{4}+9)=1\times
7\times 25$. The fact that $133=7\times 19$ is a coincidence. However, $B$ was
chosen to demonstrate that $\mathcal{M}_{n}$ can be non-invertible. Consider
the following summation:

$\displaystyle S$ $\displaystyle=\sum_{i=0}^{m-1}(-1)^{i+1}2^{2(m-1-i)}\times
2^{\frac{i(i+1)}{2}},$
$\displaystyle=\sum_{i=0}^{m-1}(-1)^{i+1}2^{\frac{4m+i^{2}-3i-4}{2}},$
$\displaystyle=-2^{2m-2}+2^{2m-3}-2^{2m-3}+2^{2m-2}+\sum_{i=4}^{m-1}(-1)^{i+1}2^{2(m-1-i)}\times
2^{\frac{i(i+1)}{2}}.$

In our case, $m=4$ and the right-hand sum vanishes. Thus we have,

$S=-64+32-32+64=0.$

That is to say,
$\mathcal{M}_{133}\overrightarrow{\mathfrak{-4}}^{4}=\overrightarrow{0}$. We
found this because $2^{8}-(-4)^{4}=0$. This is not in the domain of the
function $C_{\gamma}$, but is the reason $\mathcal{M}_{133}$ is non-
invertible. This will be explored again in chapter four.

######  Proposition 3.2.11.

Fix $\gamma\in\mathbb{Z}_{>1}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of the
$3x+\gamma$ problem of length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $\mathcal{M}_{n}$ be
constructed as by Equation (3.5). Finally suppose the quantity
$(2^{\rho}-3^{\nu})$ is prime. If $\gamma$ divides each component of $[n]$,
then $\det(\mathcal{M}_{n})\equiv 0\pmod{2^{\rho}-3^{\nu}}$.

###### Proof.

$\mathcal{M}_{n}\overrightarrow{\mathfrak{3}}^{\nu}=\frac{[n]}{\gamma}(2^{\rho}-3^{\nu})\equiv\overrightarrow{0}{\pmod{2^{\rho}-3^{\nu}}}$.
Hence $\det(\mathcal{M}_{n})\equiv 0{\pmod{2^{\rho}-3^{\nu}}}$. ∎

######  Example 26.

Consider the integral loop induced by $n=7$ and $\gamma=7$. We find that
$\rho=4$ and $\nu=2$ such that $2^{4}-3^{2}=7$. The matrix $\mathcal{M}_{7}$
has two repeated rows and thus its determinant vanishes. Consequently,
$\det(\mathcal{M}_{7})=0\equiv 0\pmod{7}$.

###  3.3 Construction of Matrix $\mathcal{R}_{n}$

####  3.3.1 Classical Results of Linear Algebra

######  Definition 3.3.1.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{1},...,x_{n}\in\mathbb{C}$. We define the
Vandermode matrix[13] $\mathcal{V}(x_{1},...,x_{n})$ as,

$\mathcal{V}(x_{1},...,x_{n})=\begin{bmatrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{n-1}\\\
1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{n-1}\end{bmatrix}.$

######  Lemma 3.3.1.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{1},...,x_{n}\in\mathbb{C}$. Let
$\mathcal{V}(x_{1},...,x_{n})$ be a Vandermode matrix. Then,

$\det(\mathcal{V}(x_{1},...,x_{n}))=\prod_{1\leq i<j\leq n}(x_{j}-x_{i}).$
(3.7)

###### Proof.

We will prove by induction[13]. The case $n=1$ is trivial. Consider the case
$n=2$:

$\det(\mathcal{V}(x_{1},x_{2}))=\left|\begin{matrix}1&x_{1}\\\
1&x_{2}\end{matrix}\right|=x_{2}-x_{1}.$

Now suppose the Equation (3.7) holds up to $n-1$. Then for a Vandermode matrix
of order $n$ we have,

$\displaystyle\det(\mathcal{V}(x_{1},...,x_{n}))$
$\displaystyle=\left|\begin{matrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{n-1}\\\
1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{n-1}\end{matrix}\right|_{n\times n},$
$\displaystyle=\left|\begin{matrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{n-1}\\\
0&x_{2}-x_{1}&x_{2}^{2}-x_{1}^{2}&\cdots&x_{2}^{n-1}-x_{1}^{n-1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&x_{n}-x_{1}&x_{n}^{2}-x_{1}^{2}&\cdots&x_{n}^{n-1}-x_{1}^{n-1}\end{matrix}\right|_{n\times
n},$
$\displaystyle=\left|\begin{matrix}x_{2}-x_{1}&x_{2}^{2}-x_{1}^{2}&\cdots&x_{2}^{n-1}-x_{1}^{n-1}\\\
\vdots&\vdots&\ddots&\vdots\\\
x_{n}-x_{1}&x_{n}^{2}-x_{1}^{2}&\cdots&x_{n}^{n-1}-x_{1}^{n-1}\end{matrix}\right|_{(n-1)\times(n-1)}.$

Where the subscript $n\times n$ indicates the size of the determinant.

$\displaystyle\det$ $\displaystyle(\mathcal{V}(x_{1},...,x_{n}))$
$\displaystyle=\left|\begin{bmatrix}x_{2}-x_{1}&0&0&\cdots&0\\\
0&x_{3}-x_{1}&0&\cdots&0\\\ 0&0&x_{4}-x_{1}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&x_{n}-x_{1}\end{bmatrix}\begin{bmatrix}1&x_{2}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{2}^{n-2-i}x_{1}^{i}\\\
1&x_{3}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{3}^{n-2-i}x_{1}^{i}\\\
\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{n}^{n-2-i}x_{1}^{i}\\\
\end{bmatrix}\right|,$
$\displaystyle=\prod_{j=2}^{n}(x_{j}-x_{1})\left|\begin{matrix}1&x_{2}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{2}^{n-2-i}x_{1}^{i}\\\
1&x_{3}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{3}^{n-2-i}x_{1}^{i}\\\
\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}+x_{1}&\cdots&\sum_{i=0}^{n-2}x_{n}^{n-2-i}x_{1}^{i}\\\
\end{matrix}\right|,$
$\displaystyle=\prod_{j=2}^{n}(x_{j}-x_{1})\left|\begin{bmatrix}1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{n-1}\\\
1&x_{3}&x_{3}^{2}&\cdots&x_{3}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{n-1}\end{bmatrix}\begin{bmatrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{n-2}\\\
0&1&x_{1}&\cdots&x_{1}^{n-3}\\\ 0&0&1&\cdots&x_{1}^{n-4}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&1\end{bmatrix}\right|,$
$\displaystyle=\prod_{j=2}^{n}(x_{j}-x_{1})\left|\begin{matrix}1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{n-1}\\\
1&x_{3}&x_{3}^{2}&\cdots&x_{3}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{n-1}\end{matrix}\right|.$

We then conclude by the induction hypothesis that the matrix determinant
matches Equation (3.7). Thus we have,

$\det(\mathcal{V}(x_{1},...,x_{n}))=\prod_{j=2}^{n}(x_{j}-x_{1})\prod_{2\leq
i<j\leq n}(x_{j}-x_{i})=\prod_{1\leq i<j\leq n}(x_{j}-x_{i})$

∎

######  Definition 3.3.2.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{0},...,x_{n-1}\in\mathbb{C}$. We define the
Circulant matrix[28][19] $\mathcal{R}(x_{0},...,x_{n-1})$ as,

$\mathcal{R}(x_{0},...,x_{n-1})=\sum_{i=0}^{n-1}x_{i}\mathcal{P}^{i}=\begin{bmatrix}x_{0}&x_{1}&x_{2}&\cdots&x_{n-2}&x_{n-1}\\\
x_{n-1}&x_{0}&x_{1}&\cdots&x_{n-3}&x_{n-2}\\\
x_{n-2}&x_{n-1}&x_{0}&\cdots&x_{n-4}&x_{n-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
x_{2}&x_{3}&x_{4}&\cdots&x_{0}&x_{1}\\\
x_{1}&x_{2}&x_{3}&\cdots&x_{n-1}&x_{0}\end{bmatrix}.$ (3.8)

######  Example 27.

Consider the numbers $0,1,2$ and $3$ in that order. Then the circulant matrix
$\mathcal{R}(0,1,2,3)$ appears as,

$\mathcal{R}(0,1,2,3)=\sum_{j=0}^{3}j\mathcal{P}^{j}=\begin{bmatrix}0&1&2&3\\\
3&0&1&2\\\ 2&3&0&1\\\ 1&2&3&0\end{bmatrix}.$

######  Proposition 3.3.2.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{0},...,x_{n-1}\in\mathbb{C}$. Let
$\mathcal{R}(x_{0},...,x_{n-1})$ be a Circulant matrix[31]. Let
$\epsilon=e^{\frac{2\pi i}{n}}$ be a primitive $n$-th root of unity. Then,

$\det(\mathcal{R}(x_{0},...,x_{n-1}))=\prod_{k=0}^{n-1}\left(\sum_{h=0}^{n-1}x_{h}\epsilon^{kh}\right).$
(3.9)

###### Proof.

Let $\omega$ be any $n$-th root of unity and consider the vector,

$\overrightarrow{v}=\begin{bmatrix}1\\\ \omega\\\ \omega^{2}\\\ \vdots\\\
\omega^{n-1}\end{bmatrix}$

Consider the first component in the product
$\mathcal{R}(x_{0},...,x_{n-1})\overrightarrow{v}$,

$x_{0}+x_{1}\omega+x_{2}\omega^{2}+...+x_{n-1}\omega^{n-1}:=\lambda.$

The second component in the product
$\mathcal{R}(x_{0},...,x_{n-1})\overrightarrow{v}$ is a multiple of $\lambda$,

$\displaystyle x_{n-1}+x_{0}\omega+x_{1}\omega^{2}+...+x_{n-2}\omega^{n-1}$
$\displaystyle=(x_{n-1}\omega^{n-1}+x_{0}+x_{1}\omega+...+x_{n-2}\omega^{n-2})\omega,$
$\displaystyle=\lambda\omega.$

In general we find the $i$-th component of
$\mathcal{R}(x_{0},...,x_{n-1})\overrightarrow{v}$ is $\omega^{i-1}\lambda$.
Thus
$\mathcal{R}(x_{0},...,x_{n-1})\overrightarrow{v}=\lambda\overrightarrow{v}$.
As $\overrightarrow{v}$ is not the zero vector, we conclude it is an
eigenvector with eigenvalue $\lambda$. The same property is true for any
$n$-th root of unity. Thus let $\omega=\epsilon^{k}$ for $0\leq k\leq n-1$.
Thus,

$\overrightarrow{v_{k}}=\begin{bmatrix}1\\\ \epsilon^{k}\\\ \epsilon^{2k}\\\
\vdots\\\ \epsilon^{(n-1)k}\end{bmatrix}.$

is an eigenvector with eigenvalue,

$\lambda_{k}=x_{0}+x_{1}\epsilon^{k}+x_{2}\epsilon^{2k}+...+x_{n-1}\epsilon^{(n-1)k}.$

Furthermore, the vectors $\overrightarrow{v_{k}}$ are linearly independent.
Consider the matrix $B$ whose columns the vectors $\overrightarrow{v_{k}}$.

$B=\begin{bmatrix}1&1&1&\cdots&1\\\
1&\epsilon&\epsilon^{2}&\cdots&\epsilon^{n-1}\\\
1&\epsilon^{2}&\epsilon^{4}&\cdots&\epsilon^{2(n-1)}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\epsilon^{n-1}&\epsilon^{2(n-1)}&\cdots&\epsilon^{(n-1)(n-1)}\\\
\end{bmatrix}.$

$B$ is a Vandermode matrix. By Lemma 3.3.1 we have proven the determinant of
$B$ is $\prod_{0\leq i<j\leq n-1}(\epsilon^{j}-\epsilon^{i})\neq 0$. Thus $B$
is nonsingular, and $\lambda_{k}$ for $0\leq k\leq n-1$ are the eigenvalues of
$\mathcal{R}(x_{0},...,x_{n-1})$. As the determinant of a matrix is the
product of its eigenvalues. Thus we have,

$\det(\mathcal{R}(x_{0},...,x_{n-1}))=\prod_{k=0}^{n-1}\lambda_{k}=\prod_{k=0}^{n-1}\left(\sum_{h=0}^{n-1}x_{h}\epsilon^{kh}\right).$

∎

######  Definition 3.3.3.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{0},...,x_{n-1}\in\mathbb{C}$. Let
$\mathcal{R}(x_{0},...,x_{n-1}$ be a Circulant matrix. We call
$f(w)=x_{0}+x_{1}w+x_{2}w^{2}+...+x_{n-1}w^{n-1}$ the associated polynomial to
$\mathcal{R}(x_{0},...,x_{n-1})$.

######  Lemma 3.3.3.

Fix $n\in\mathbb{Z}_{>0}$ and $x_{0},...,x_{n-1}\in\mathbb{C}$. Let
$\mathcal{R}(x_{0},...,x_{n-1})$ be a Circulant matrix. Then the rank of
$\mathcal{R}(x_{0},...,x_{n-1})$ is $n-d$, where $d$ is the degree of
polynomial $g(w)=\gcd(f(w),w^{n}-1)$[12] .

###### Proof.

Let $\mu_{n}$ be the set of complex solutions to $w^{n}-1$. It is immediate
that we can rewrite Equation (3.9) in terms of $f(w)$.

$\det(\mathcal{R}(x_{0},...,x_{n-1}))=\prod_{k=0}^{n-1}\left(\sum_{h=0}^{n-1}x_{h}\epsilon^{kh}\right)=\prod_{\zeta\in\mu_{n}}f(\zeta).$

Thus $f(w)$ vanishes if and only if $w^{n}-1$ have a common zero. ∎

######  Lemma 3.3.4.

Fix $n,p\in\mathbb{Z}_{>0}$ and $x_{0},...,x_{n-1}\in\mathbb{C}$. Let $p$ be
prime with $p\nmid n$. Let $\mathcal{R}(x_{0},...,x_{n-1})$ be a Circulant
matrix. Then $\det(\mathcal{R}(x_{0},...,x_{n-1}))\equiv 0\pmod{p}$ if and
only if $f(w)$ and $w^{n}-1$ share a common zero[12] .

###### Proof.

Write $n=p^{t}m$ for some $t,m\in\mathbb{Z}$ and $p\nmid m$. Then
$w^{n}-1=(w^{m}-1)^{p^{t}}$. Following from Lemma 3.3.3,

$\det(\mathcal{R}(x_{0},...,x_{n-1}))=\prod_{\zeta\in\mu_{m}}f(\zeta)^{p^{t}}.$

Where $\mu_{m}$ is the $m$ roots of unity in the algebraic closure of the
field $\mathbb{F}_{p}$. ∎

####  3.3.2 A Second Theorem Regarding the Determinant of $\mathcal{M}_{n}$

######  Theorem 3.3.5.

Fix $n\in\mathbb{Z}_{>0}$. Let $F(n)$ be the number of $n$-tuples
$(x_{0},x_{1},...,x_{n-1})$ satisfying[4],

$\displaystyle x_{i}\geq 0$ $\displaystyle,(i=0,1,...,n-1)$
$\displaystyle\sum_{i=0}^{n-1}x_{i}$ $\displaystyle=n,$
$\displaystyle\sum_{i=0}^{n-1}ix_{i}$ $\displaystyle\equiv 0\pmod{n}.$

Then,

$F(n)=\frac{1}{n}\sum_{d|n}{{2d-1}\choose d}\phi\left(\frac{n}{d}\right),$

where the summation extends over all positive integers $d$ dividing $n$, and
where $\phi$ is Euler’s function.

###### Proof.

Define $f_{n}(w,z)=[(1-z)(1-wz)...(1-w^{n-1}z)]^{-1}$. Then,

$f_{n}(w,z)=\left(\sum_{k=0}^{\infty}z^{k}\right)\left(\sum_{k=0}^{\infty}w^{k}z^{k}\right)...\left(\sum_{k=0}^{\infty}w^{k(n-1)}z^{k}\right).$

$F(n)$ is the sum of coefficients of $z^{n}w^{nt}$, for $0\leq t\leq n-1$, in
$f_{n}(w,z)$. Write $f_{n}(w,z)=\sum_{k=0}^{\infty}B_{k}z^{k}=B_{k}(n,w)$.
Then because,

$f_{n+1}(w,z)=\frac{f_{n}(w,z)}{1-w^{n}z},$

and $f_{n}(w,wz)=[(1-wz)(1-w^{2}z)...(1-w^{n}z)]^{-1}$, then
$f_{n}(w,wz)=(1-z)f_{n+1}(w,z)=\frac{1-z}{1-w^{n}z}f_{n}(w,z)$. Thus,

$\displaystyle\sum_{k=0}^{\infty}B_{k}w^{k}z^{k}$
$\displaystyle=\frac{1-z}{1-w^{n}z}\sum_{k=0}^{\infty}B_{k}z^{k},$
$\displaystyle\sum_{k=0}^{\infty}B_{k}w^{k}z^{k}-\sum_{k=0}^{\infty}B_{k}w^{n+k}z^{k+1}$
$\displaystyle=\sum_{k=0}^{\infty}B_{k}z^{k}-\sum_{k=0}^{\infty}B_{k}z^{k+1}.$

Hence for $k\geq 1$, $B_{k}w^{k}-B_{k-1}w^{n+k-1}=B_{k}-B_{k-1}$, or

$B_{k}=\frac{1-w^{n+k-1}}{1-w^{k}}B_{k-1},(k\geq 1).$

Since $B_{0}=1$, then $B_{k}=\prod_{r=1}^{k}\frac{1-w^{n+r-1}}{1-w^{r}}$,
$(k\geq 0)$. With empty product being 1. Therefore,

$f_{n}(w,z)=\sum_{k=0}^{\infty}\left\\{\prod_{r=1}^{k}\frac{1-w^{n+r-1}}{1-w^{r}}\right\\}z^{k},$

and $F(n)$ is the sum of the coefficients of $w^{nt}$, $0\leq t\leq n-1$, in
$g_{n}(w)=\prod_{r=1}^{n}\frac{1-w^{n+r-1}}{1-w^{r}}=\prod_{r=1}^{n-1}\frac{1-w^{n+r}}{1-w^{r}}$.
$g_{n}(w)$ is a polynomial in $w$ of degree
$\sum_{r=1}^{n-1}\\{n+r-r\\}=n(n-1)$ and has nonnegative coefficients. Since,

$\sum_{\zeta\in\mu_{n}}\zeta^{k}=\left\\{\begin{matrix}n,\text{if $n$ divides
$k$}\\\ 0,\text{else,}\end{matrix}\right.$

we have $nF(n)=\sum_{\zeta\in\mu_{n}}g_{n}(\zeta)$, where the summation
extends over all $n$-th roots of unity. Suppose $\zeta$ is a primitive $d$-th
root of unity where $d|n$. Since,

$\lim_{w\to\zeta}\frac{1-w^{n+r}}{1-w^{r}}=\left\\{\begin{matrix}\frac{n+r}{r},\text{
if $d$ divides $r$}\\\ 1,\text{ else.}\end{matrix}\right.$

Then we have that,

$g_{n}(\zeta)=\prod_{1\leq r\leq n-1\\\ r\equiv
0\pmod{d}}\frac{n+r}{r}=\prod_{s=1}^{\frac{n}{d}-1}\frac{n+sd}{sd}={{2\frac{n}{d}-1}\choose{\frac{n}{d}}}.$

Therefore, since there are $\phi(d)$ $n$-th roots of unity which are primitive
$d$-th roots of unity,

$F(n)=\frac{1}{n}\sum_{d|n}{{2\frac{n}{d}-1}\choose{\frac{n}{d}}}\phi\left(d\right)=\frac{1}{n}\sum_{d|n}{{2d-1}\choose
d}\phi\left(\frac{n}{d}\right).$

∎

######  Definition 3.3.4.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Let the quantities
$m_{j}$ be given by Proposition 2.1.2. Let $z_{1},...,z_{\nu}$ be defined by,

$z_{i}=2^{\frac{1}{\nu}\sum_{k=1}^{\nu-1}km_{|i+k-2|_{\nu}+1}}.$ (3.10)

Where $|i+k-2|_{\nu}$ is $i+k-2$ modulo $\nu$. Then we define the circulant
matrix $\mathcal{R}_{n}$ associated to $n$ as,

$\mathcal{R}_{n}=\mathcal{R}(z_{1},...,z_{\nu})=\sum_{j=1}^{\nu}z_{j}\mathcal{P}^{j-1}.$
(3.11)

######  Example 28.

Consider the integral loop induced by $n=19$ and $\gamma=485$. In this case a
single period of $B=101010000000$ with $m_{1}=1,m_{2}=1$ and $m_{3}=7$.
Solving for the coefficients of $z_{1},z_{2}$, and $z_{3}$ we have:

$\displaystyle z_{1}$
$\displaystyle=2^{\frac{m_{1}+2m_{2}}{3}}=2^{\frac{1+2\times 1}{3}}=2,$
$\displaystyle z_{2}$
$\displaystyle=2^{\frac{m_{2}+2m_{3}}{3}}=2^{\frac{1+2\times 7}{3}}=32,$
$\displaystyle z_{3}$
$\displaystyle=2^{\frac{m_{3}+2m_{1}}{3}}=2^{\frac{7+2\times 1}{3}}=8.$

Finally $\mathcal{R}_{19}$ appears as,

$\mathcal{R}_{19}=\mathcal{R}(2,32,8)=\begin{bmatrix}2&32&8\\\ 8&2&32\\\
32&8&2\end{bmatrix}.$

For the following, let $S_{n}$ be the symmetric group acting on $n$ elements.

######  Lemma 3.3.6.

Fix $n\in\mathbb{Z}_{>0}$. Let
$a_{0},...,a_{n-1},b_{0},...,b_{n-1}\in\mathbb{R}_{>0}$. Define
$\mathcal{R}(a_{0},...,a_{n-1})$ as by Equation (3.8) and
$\mathcal{M}(b_{0},...,b_{n-1})$ by Equation (3.12) below,

$\mathcal{M}(b_{0},...,b_{n-1})=\begin{bmatrix}1&b_{0}&b_{0}b_{1}&...&b_{0}b_{1}...b_{n-2}\\\
1&b_{1}&b_{1}b_{2}&...&b_{1}b_{2}...b_{n-1}\\\ \vdots&\vdots&\ddots&\vdots\\\
1&b_{n-2}&b_{n-2}b_{n-1}&...&b_{n-2}b_{n}...b_{n-4}\\\
1&b_{n-1}&b_{n-1}b_{0}&...&b_{n-1}b_{0}...b_{n-3}\end{bmatrix}.$ (3.12)

Then there is a one to one correspondence between the polynomial terms that
appear in the determinant of $\mathcal{R}(a_{0},...,a_{n-1})$ and
$\mathcal{M}(b_{0},...,b_{n-1})$.

###### Proof.

Let $r_{i,j}$ be the element of matrix $\mathcal{R}(a_{0},...,a_{n-1})$ and
$s_{i,j}$ be the element of matrix $\mathcal{M}(b_{0},...,b_{n-1})$ at the
$i$-th row and $j$-th column, respectively. Recall the definition of the
determinant.

$\displaystyle\det(\mathcal{R}(a_{0},...,a_{n-1}))$
$\displaystyle=\sum_{\sigma\in
S_{n}}sgn(\sigma)\prod_{i=1}^{n}r_{i,\sigma(i)},$
$\displaystyle\det(\mathcal{M}(b_{0},...,b_{n-1}))$
$\displaystyle=\sum_{\sigma\in
S_{n}}sgn(\sigma)\prod_{i=1}^{n}s_{i,\sigma(i)}.$

Fix $\sigma\in S_{n}$. Then for some $A,A^{\prime}\in\mathbb{Z}$, we have
$Ar_{1,\sigma(1)}...r_{n,\sigma(n)}=Aa_{0}^{y_{0}}...a_{n-1}^{y_{n-1}}$ for
some $y_{0},...,y_{n-1}\in\mathbb{Z}_{\geq 0}$ and
$A^{\prime}s_{1,\sigma(1)}...s_{n,\sigma(n)}=A^{\prime}b_{0}^{w_{0}}...b_{n-1}^{w_{n-1}}$
for some $w_{0},...,w_{n-1}\in\mathbb{Z}_{\geq 0}$. The former is a polynomial
of degree $n$, and the latter is a polynomial of degree $n(n-1)/2$. Consider
first the permutations $\sigma_{k}(i)=i+k$ for $0\leq k\leq n-1$. We find that
each corresponds to the monomial $a_{k}^{n}$. Let $\theta\in S_{n}$ be the
permutation $(1,n)(2,n-1)...(\frac{n+1}{2},\frac{n+1}{2})$ if $n$ is odd and
$(1,n)(2,n-1)...(\frac{n}{2}-1,\frac{n}{2}+1)$ if $n$ is even. We see that for
all $\sigma\in S_{n}$, $\theta\circ\sigma(i)=n+1-\sigma(i)$. As each
permutation is an automorphism of $S_{n}$, then we can freely choose to
compose $\theta$ and $\sigma$ in the definition of the determinant for
$\mathcal{M}(b_{0},...,b_{n-1})$ without changing the result. We find that the
matrix determinants of $\mathcal{R}(a_{0},...,a_{n-1})$ and
$\mathcal{M}(b_{0},...,b_{n-1})$ have a one to one correspondence if and only
if for each $a_{k}$ $(0\leq k\leq n-1)$ we have:

$a_{k}^{n}=b_{|n-k|_{n}}^{1}b_{|n+1-k|_{n}}^{2}b_{|n+2-k|_{n}}^{3}...b_{|n-1-k|_{n}}^{n-1}.$

Where $|n-k|_{n}$ denotes $n-k$ modulo $n$. Let $e_{1},...,e_{n}$ and
$\tilde{e}_{1},...,\tilde{e}_{n}$ represent two bases for the space
$\mathbb{R}^{n}$. Then let us make the following substitution,
$a_{k}^{y_{k}}\rightarrow y_{k-1}e_{k}$ and $b_{k}^{w_{k}}\rightarrow
w_{k-1}\tilde{e}_{k}$. We find that the exponents of each polynomial term
associated to $\mathcal{R}(a_{0},...,a_{n-1})$ corresponds to a polynomial
term associated to $\mathcal{M}(b_{0},...,b_{n-1})$ by the following linear
transformation:

$\frac{1}{n}\begin{bmatrix}1&0&n-1&n-2&\dots&2\\\ 2&1&0&n-1&\dots&3\\\
3&2&1&0&\dots&4\\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&n-1&n-2&n-3&\dots&1\end{bmatrix}\begin{bmatrix}y_{0}\\\ y_{1}\\\ y_{2}\\\
\vdots\\\ y_{n-1}\end{bmatrix}=\begin{bmatrix}w_{0}\\\ w_{1}\\\ w_{2}\\\
\vdots\\\ w_{n-1}\end{bmatrix}.$ (3.13)

The determinant of the above linear transformation is $n^{n-1}(n-1)/2$, which
is non-vanishing. Conversely, if we were to start with exponents of each
polynomial term associated to $\mathcal{M}(b_{0},...,b_{n-1})$ and relate them
to the exponents of the polynomial terms of $\mathcal{R}(a_{0},...,a_{n-1})$
we would find an analogous result with the matrix inverse of Equation (3.13).

$\small\begin{bmatrix}y_{0}\\\ y_{1}\\\ y_{2}\\\ \vdots\\\
y_{n-1}\end{bmatrix}=\frac{2}{n(n-1)}\begin{bmatrix}1&1&\dots&1&\frac{2+n(n-1)}{2}&\frac{2-n(n-1)}{2}\\\
\frac{2-n(n-1)}{2}&1&\dots&1&1&\frac{2+n(n-1)}{2}\\\
\frac{2+n(n-1)}{2}&\frac{2-n(n-1)}{2}&\dots&1&1&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
1&1&\dots&\frac{2+n(n-1)}{2}&\frac{2-n(n-1)}{2}&1\end{bmatrix}\begin{bmatrix}w_{0}\\\
w_{1}\\\ w_{2}\\\ \vdots\\\ w_{n-1}\end{bmatrix}.$ (3.14)

However, by Theorem 3.3.5 that a necessary and sufficient condition for a
polynomial term to exist in the permanent of $\mathcal{R}(a_{0},...,a_{n-1})$
is that $\sum_{i}iy_{i}\equiv 0\pmod{n}$. Call the matrix in Equation (3.14),
$\theta_{j,k}$. Thus we find that,

$\sum_{j=0}^{n-1}y_{j}=n,\hskip 14.22636pt\sum_{j=0}^{n-1}jy_{j}\equiv
0\pmod{n},$

if and only if,

$\sum_{j=0}^{n-1}\left(\sum_{k=0}^{n-1}\theta_{j+1,k+1}w_{k}\right)=n,\hskip
14.22636pt\sum_{j=0}^{n-1}j\left(\sum_{k=0}^{n-1}\theta_{j+1,k+1}w_{k}\right)\equiv
0\pmod{n}.$

As $\theta_{j,k}$ is invertible, we conclude that there is a one to one
correspondence between the polynomial terms that appear in the determinant of
$\mathcal{R}(a_{0},...,a_{n-1})$ and $\mathcal{M}(b_{0},...,b_{n-1})$. ∎

######  Proposition 3.3.7.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Let $\mathcal{M}_{n}$
be constructed as by Equation (3.5). Let $\mathcal{R}_{n}$ be constructed by
Definition 3.3.4. Then the following equality is satisfied,

$\left|\det(\mathcal{M}_{n})\right|=\left|\det(\mathcal{R}_{n})\right|.$

###### Proof.

Fix $\sigma\in S_{\nu}$. Let $\theta\in S_{n}$ be the permutation
$(1,\nu)(2,\nu-1)...(\frac{\nu+1}{2},\frac{\nu+1}{2})$ if $\nu$ is odd and
$(1,\mu)(2,\nu-1)...(\frac{\nu}{2}-1,\frac{\nu}{2}+1)$ if $\nu$ is even.
Following from Lemma 3.3.6 we recall that the polynomial terms of
$\det(\mathcal{M}_{n})$ and $\det(\mathcal{R}_{m})$ have a one to one
correspondence. For a single polynomial term $\mathcal{R}_{n}$, we have
$a_{0}^{y_{0}}...a_{\nu-1}^{y_{\nu-1}}=2^{y_{0}m_{1}+y_{1}m_{2}+...+y_{\nu-1}m_{\nu}}$,
and its corresponding polynomial term chosen by $\theta\circ\sigma$ in
$\mathcal{M}_{n}$,
$b_{0}^{w_{0}}...b_{\nu-1}^{w_{\nu-1}}=2^{w_{0}m_{1}+w_{1}m_{2}+...+w_{\nu-1}m_{\nu}}$.
The base of both polynomials is two, allowing us to compare the exponents
directly. The non-vanishing terms of $\det(\mathcal{R}_{n})$ have exponents
which coincide with the solutions to the following system of equations:

$\displaystyle\sum_{j=1}^{\nu}jy_{j}\equiv 0$ $\displaystyle\pmod{\nu},$
(3.15) $\displaystyle\sum_{j=1}^{\nu}y_{j}=\nu.$

The $y_{0},...,y_{\nu-1}$ satisfying Equation (3.15) identically match
Definition 3.3.4, and thus directly correspond to $w_{0},...,w_{\nu-1}$. Thus
the polynomial term, apart from a sign change, is identical. Thus
$\left|\det(\mathcal{M}_{n})\right|=\left|\det(\mathcal{R}_{n})\right|$. ∎

######  Example 29.

Consider the integral loop induced by $n=19$ and $\gamma=485$. We find that,

$\det(\mathcal{M}_{19})=\left|\begin{matrix}1&2&4\\\ 1&2&256\\\
1&128&256\end{matrix}\right|=-31752,\hskip
7.11317pt\det(\mathcal{R}_{19})=\left|\begin{matrix}2&32&8\\\ 8&2&32\\\
32&8&2\end{matrix}\right|=31752.$

Consider the integral loop induced by $n=19$ and $\gamma=101$. We find that,

$\det(\mathcal{M}_{19})=\left|\begin{matrix}1&2&4\\\ 1&2&64\\\
1&32&64\end{matrix}\right|=-1800,\hskip
7.11317pt\det(\mathcal{R}_{19})=\left|\begin{matrix}2&2^{11/3}&2^{7/3}\\\
2^{7/3}&2&2^{11/3}\\\ 2^{11/3}&2^{7/3}&2\end{matrix}\right|=1800.$

######  Corollary 3.3.7.1.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Let $\mathcal{M}_{n}$
be constructed as by Equation (3.5). Let $\mathcal{R}_{n}$ and be constructed
by Definition 3.11. Let $z_{j}$ be defined as by Equation (3.10). Finally let
$\epsilon$ be the $n$-th root of unity. Then the determinant[19] of
$\mathcal{M}_{n}$ can be expressed in the following formula:

$\left|\det(\mathcal{M}_{n})\right|=\left|\prod_{k=0}^{\nu-1}\sum_{h=0}^{\nu-1}z_{h+1}\epsilon^{kh}\right|.$
(3.16)

###### Proof.

This follows from Proposition 3.3.7 and Equation 3.9. ∎

Now that we have shown that the determinants of $\mathcal{M}_{n}$ and
$\mathcal{R}_{n}$ have identical prime factorization, we can utilize the
following lemma. Assume a priori $z_{1},...z_{n}\in\mathbb{Z}$.

######  Lemma 3.3.8.

Let $n$ and $p$ be distinct primes such that the residue class $p\pmod{n}$
generates the whole group $\mathbb{Z}_{n}^{*}$. Then for any circulant
$\mathcal{R}(z_{1},...,z_{n})=z_{1}\mathcal{P}^{0}+z_{2}\mathcal{P}^{1}+...z_{n}\mathcal{P}^{n-1}$
with $z_{1},...,z_{n}\in\mathbb{Z}$, the condition
$p|\det(\mathcal{R}(z_{1},...,z_{n}))$ is satisfied if and only if either
$p|(z_{1}+...+z_{n})$ or $z_{1}\equiv...\equiv z_{n}\pmod{p}$.[26]

###### Proof.

Suppose $p$ divides $\det(\mathcal{R}(z_{1},...,z_{n}))$ and recall Equation
3.9. Consider first the case $k=0$. We have the term $(z_{1}+...+z_{n})$. If
$p$ divides the sum, then we are done. Else, if $z_{1}\equiv...\equiv
z_{n}\pmod{p}$ then for $k=1$ we have
$(z_{1}+z_{2}\epsilon+...+z_{n}\epsilon^{n-1})\equiv
z_{1}(1+\epsilon+...+\epsilon^{n-1})\equiv 0\pmod{p}$. On the other hand by
Lemma 3.3.4, we know that $p\mid\det(\mathcal{R}(z_{1},...,z_{n}))$ if and
only if $\gcd(f(w),w^{n}-1)\neq c(c\in\mathbb{Z}_{p}^{*})$. Assuming that
$p\nmid(z_{1}+...+z_{n})$, then 1 is not a common root. Thus
$p\mid\det(\mathcal{R}(z_{1},...,z_{n}))$ is equivalent to
$\gcd(f(w),1+w+...+w^{n-1})\neq
c\in\mathbb{Z}_{p}[w](c\in\mathbb{Z}_{p}^{*})$. We conclude that
$p|\det(\mathcal{R}(z_{1},...,z_{n}))$ is satisfied if and only if either
$p|(z_{1}+...+z_{n})$ or $z_{1}\equiv...\equiv z_{n}\pmod{p}$. ∎

In our case, we are concerned about the contrapositive. Moreover, for the
theorem to be effective, we require that the entries of $\mathcal{R}_{n}$ are
integers. Thus we can construct the following theorem.

######  Theorem 3.3.9.

Fix $\gamma,n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$. Suppose
further $n$ starts an integral loop of length $N$. Let $B=\\{0,1\\}^{**}$ such
that $B=(\chi_{\gamma}^{i}(n))_{\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Assume $\nu$ is prime.
Let the quantities $m_{j}$ from Proposition 2.1.2 satisfy Equation (3.3.4) so
that $z_{1},...,z_{\nu}$ are integers. Let $\mathcal{R}_{n}$ be constructed by
Equation (3.11). Let $p$ be a prime factor of $2^{\rho}-3^{\nu}$ distinct from
$\nu$ so that the residue class $p\pmod{\nu}$ generates the whole group
$\mathbb{Z}_{\nu}^{*}$. Then $p\nmid\det(\mathcal{M}_{n})$ if and only if
$p\nmid(z_{1}+...+z_{\nu})$ and for some $1\leq i<j\leq\nu$ we have
$z_{i}\not\equiv z_{j}\pmod{p}$.

###### Proof.

Recall from Proposition 3.3.7 that
$|\det(\mathcal{M}_{n})|=|\det(\mathcal{R}_{n})|$. Then consider the
contrapositive of Lemma 3.3.8. ∎

######  Example 30.

Consider the integral loop induced by $n=19$ and $\gamma=485$. In this case
$m_{1}=1,m_{2}=1$ and $m_{3}=7$ such that $2^{9}-3^{3}=485=5\times 97$. We
find that $z_{1}=2,z_{2}=32$ and $z_{3}=8$. Thus $\mathcal{R}_{19}$ has all
integer coefficients. The prime factor 5 is in the residue class of 2, which
generates the whole group $\mathbb{Z}_{3}^{*}$. We find that $2+32+8=42\equiv
2\pmod{5}$. Furthermore $2\equiv 2\pmod{5}$ and $8\equiv 3\pmod{5}$. Thus by
the theorem we conclude that $\det(\mathcal{M}_{19})$ is nonsingular modulo 5.
Finally $\det(\mathcal{M}_{19})\not\equiv 0\pmod{2^{9}-3^{3}}$.

######  Example 31.

Consider the integral loop induced by $n=184337$ and $\gamma=1048333$. In this
case $m_{1}=6,m_{2}=2,m_{3}=6,m_{4}=3$ and $m_{5}=3$ such that
$2^{20}-3^{5}=1048333=11\times 13\times 7331$. We find that
$z_{1}=256,z_{2}=128,z_{3}=512,z_{4}=128$ and $z_{5}=512$. Thus
$\mathcal{R}_{184337}$ has all integer coefficients. The prime factors 11 and
7331 are both in the residue class of 1, and cannot be used. However, the
residue class of 13 is 3, which indeed generates the whole group
$\mathbb{Z}_{5}^{*}$. We find that $256+128+512+128+512=1536\equiv
2\pmod{13}$. Furthermore $256\equiv 9\pmod{13}$ and $128\equiv 11\pmod{13}$.
Thus by the theorem we conclude that $\det(\mathcal{M}_{184337})$ is
nonsingular modulo 13. Finally, $\det(\mathcal{M}_{184337})\not\equiv
0\pmod{2^{20}-3^{5}}$.

##  Chapter 4 Perspectives

###  4.1 Discussion

Chapter five is broken up into four different discussions. Each discussion is
a segue into a topic related to the thesis, but not in the direct path towards
Theorem 3.3.9. Each also serves as an avenue which future research can be
taken. The first discussion is a complement to Examples (7) and (25). We
discuss first the general Exponential Diophatine Equation, then apply a
combinatorical argument to give a bound to the ratio of ones and zeros in a
finite binary sequence corresponding to an integral loop of the $3x+1$
Problem. The second and third discussions are two different methods to map
distinct integral loops of the $3x+\gamma$ problem into each other. The fourth
discussion demonstrates that the integral loop vector is the unique solution
of an eigenvector problem with eigenvalue one.

###  4.2 A Segue Into Exponential Diophantine Equations and Combinatorics

One could argue that this is the richest part of the thesis behind the thesis.
If one were to ask exactly in what manner any of the results here were
derived, it would be by the virtue of Exponential Diophantine Equations. Fix
$a,b,x,y\in\mathbb{Z}_{>0}$. Let the mapping
$f:\mathbb{Z}_{>0}^{4}\to\mathbb{Z}$ be given as,

$f(x,y,a,b)=a^{x}-b^{y}.$

Equations of this kind are exactly the ones which generate integral loops. In
our case we took $a=2$, $b=3$, $x=\rho$, and $y=\nu$. In this thesis we
consistently provided the starting integer $n$ and then chose
$B\in\\{0,1\\}^{**}$ so that $B$ matched the characteristic trajectory of $n$.
However, that is not how one finds integral loops in practice. It is much
easier to pick $\rho$ and $\nu$ first, then choose an arrangement of ones and
zeros generating $n$ by Equation (2.3). The number of integral loops follows a
classic Stars and Bars type problem[1]. Let $\rho,\nu\in\mathbb{Z}_{>0}$ so
that $2^{\rho}-3^{\nu}\geq 0$. Then the number of integral loops is bounded
above by the following quantity:

$\\#\\{\text{integral loops with $\rho$ zeros and $\nu$
ones}\\}<{\rho-1\choose\nu-1}.$

One could even suppose that the entirety of the Collatz Conjecture can be
reduced down to a combinatorical question in an Exponential Diophantine
Equation. We will demonstrate the power of this kind of thinking with the
following proposition:

######  Proposition 4.2.1.

Let $\gamma=1$. Fix $n\in\mathbb{Z}_{>0}^{odd}$ and $N\in\mathbb{Z}_{>0}$.
Suppose $n$ starts an integral loop of length $N$. Let $B\in\\{0,1\\}^{**}$
such that $B=(\chi^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of
the number of zeros and ones in a single period of $B$. Then the ratio
$\rho/\nu$ must satisfy the following inequality:

$\frac{\ln(3)}{\ln(2)}<\frac{\rho}{\nu}\leq 2.$

###### Proof.

The lower bound is a direct consequence of the Integral Loop Formula. As for
the upper bound, we will demonstrate by construction. Let $\nu$ be a fixed
positive integer. We observe first that the ratio $\rho/\nu$ increases if and
only if $2^{\rho}-3^{\nu}$ increases. Recall the indexing sequence $i_{j}$ of
Equation (2.2.1). In this case let $n_{j}$ denote the $(j-1)$th odd number in
the integral loop starting with $n_{1}$. Then we have the following system of
equations:

$\left\\{\begin{array}[]{lll}2^{m_{j}}&=\frac{3n_{j}+1}{n_{j+1}},&1\leq
j\leq\nu-1,\\\ 2^{m_{\nu}}&=\frac{3n_{\nu-1}+1}{n_{1}}.&\end{array}\right.$
(4.1)

Observe that the product of terms is $2^{\rho}$:

$\frac{(3n_{1}+1)(3n_{2}+1)...(3n_{\nu-1}+1)(3n_{\nu}+1)}{n_{1}n_{2}...n_{\nu-1}n_{\nu}}=2^{\rho}=(2^{\rho}-3^{\nu})+3^{\nu}.$
(4.2)

We can reduce the product down to the following equation:

$2^{\rho}-3^{\nu}=\frac{1+\sum_{i=1}^{\nu-1}\frac{3^{i}}{i!}\left(\sum_{\sigma\in
S(\nu)}\prod_{k=1}^{i}n_{\sigma(i)}\right)}{\prod_{i=1}^{\nu}n_{i}}.$ (4.3)

Equation (4.3) is maximized when the denominator is minimized. Thus, the
largest value of $2^{\rho}-3^{\nu}$ is obtained when
$n_{1}=n_{2}=...n_{\nu}=1$. Equation (4.3) reduces to:

$\displaystyle 2^{\rho}-3^{\nu}$
$\displaystyle=\sum_{i=0}^{\nu-1}3^{i}{\nu\choose i},$ (4.4) $\displaystyle
2^{\rho}$ $\displaystyle=\sum_{i=0}^{\nu}3^{i}{\nu\choose
i}=4^{\nu}=2^{2\nu}.$

We conclude that with $\nu$ being a fixed positive integer, the largest value
$\rho$ can attain is $2\nu$ satisfying the upper inequality. ∎

######  Example 32.

Let $\rho=9$ and $\nu=4$. Then the ratio $\rho/\nu=9/4>2$. We know there are a
total of 56 integral loops starting with a one. Of these 56 integral loops, we
can combine them into 14 groups of four, corresponding to the same trajectory
but with different starting numbers. We observe that in each of these integral
loops, there is at least one odd positive integer in the integral loop smaller
than $2^{9}-3^{4}=431$. Thus none of the integral loops within the $3x+431$
problem correspond to an integral loop of the $3x+1$ problem.

$B$ |  $3x+431$ Integral Loop |  $3x+1$ Integral Loop (approx.)
---|---|---
| 1001001001000
---
1001001000100
1001000100100
1000100100100
| $\\{175,956,478,$
---
$239,1148,574,$
$287,1292,646,$
$323,1400,700,350\\}$
| $\\{0.406,2.218,1.109,$
---
$0.554,2.663,1.331,$
$0.665,2.997,1.498,$
$0.749,3.248,1.624,0.812\\}$
| 1010101000000
---
1010100000010
1010000001010
1000000101010
| $\\{65,626,313,$
---
$1370,685,2486,$
$1243,4160,2080,$
$1040,520,260,130\\}$
| $\\{0.150,1.452,0.726,$
---
$3.178,1.589,5.767,$
$2.883,9.651,4.825,$
$2.412,1.206,0.603,0.301\\}$
| 1010100100000
---
1010010000010
1001000001010
1000001010100
| $\\{73,650,325,$
---
$1406,703,2540,$
$1270,635,2336,$
$1168,584,292,146\\}$
| $\\{0.169,1.508,0.754,$
---
$3.262,1.631,5.893,$
$2.946,1.473,5.419,$
$2.709,1.354,0.677,0.338\\}$
| 1001010100000
---
1010100000100
1010000010010
1000001001010
| $\\{103,740,370,$
---
$185,986,493,$
$1910,955,3296,$
$1648,824,412,206\\}$
| $\\{0.238,1.716,0.858,$
---
$0.429,2.287,1.143,$
$4.431,2.215,7.647,$
$3.823,1.911,0.955,0.477\\}$

######  Corollary 4.2.1.1.

###  4.3 A Segue Into The Special Linear Group

Let $\overrightarrow{\mathfrak{1}}^{\nu}$ denote the $\nu\times 1$ vector of
all ones.

######  Proposition 4.3.1.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let the matrix
$\mathcal{D}_{n}$ given by Equation (3.3). Then the integral loop vector $[n]$
associated to $n$ and $\mathcal{D}_{n}$ satisfy the following equalities:

$\displaystyle{}[n]$
$\displaystyle=\frac{\gamma}{2^{\rho}-3^{\nu}}\sum_{i=0}^{\nu-1}3^{\nu-1-i}(D_{n}^{i}\overrightarrow{\mathfrak{1}}^{\nu}),$
(4.5) $\displaystyle[n]$
$\displaystyle=\gamma(D_{n}-3\mathbb{I}_{\nu})^{-1}\overrightarrow{\mathfrak{1}}^{\nu}.$

Where $\mathcal{D}_{n}\overrightarrow{\mathfrak{1}}^{\nu}$ is standard
multiplication of a $\nu\times\nu$ matrix and a $\nu\times 1$ vector.

###### Proof.

The first equality follows from Proposition 3.1.1 and Equation (2.4). The
second equality can be derived from the first by a series expansion:

$\displaystyle{}D_{n}[n]$
$\displaystyle=\frac{\gamma}{2^{\rho}-3^{\nu}}\left(\sum_{i=0}^{\nu-2}3^{\nu-1-i}(D_{n}^{i+1}\overrightarrow{\mathfrak{1}}^{\nu})+2^{\rho}D_{n}^{0}\overrightarrow{\mathfrak{1}}^{\nu}\right),$
$\displaystyle 3[n]$
$\displaystyle=\frac{\gamma}{2^{\rho}-3^{\nu}}\sum_{i=0}^{\nu-1}3^{\nu-i}(D_{n}^{i}\overrightarrow{\mathfrak{1}}^{\nu}),$
$\displaystyle(D_{n}-3\mathbb{I}_{\nu})[n]$
$\displaystyle=\gamma\overrightarrow{\mathfrak{1}}^{\nu},$ $\displaystyle[n]$
$\displaystyle=\gamma(D_{n}-3\mathbb{I}_{\nu})^{-1}\overrightarrow{\mathfrak{1}}^{\nu}.$

We take note that
$\det(D_{n}-3\mathbb{I}_{\nu})=(-1)^{\nu+1}(2^{\rho}-3^{\nu})\neq 0$. Thus,
both equalities have been established. ∎

######  Example 33.

Consider the integral loop induced by $n=133$ and $\gamma=943$. We verify the
second equality of Equation (4.5):

$\displaystyle 943\left(\begin{bmatrix}-3&2&0&0\\\ 0&-3&4&0\\\ 0&0&-3&8\\\
16&0&0&-3\end{bmatrix}\right)^{-1}\times\begin{bmatrix}1\\\ 1\\\ 1\\\
1\end{bmatrix}$
$\displaystyle=943\begin{bmatrix}\frac{27}{943}&\frac{18}{943}&\frac{24}{943}&\frac{64}{943}\\\
\frac{512}{943}&\frac{27}{943}&\frac{36}{943}&\frac{96}{943}\\\
\frac{384}{943}&\frac{256}{943}&\frac{27}{943}&\frac{72}{943}\\\
\frac{144}{943}&\frac{96}{943}&\frac{128}{943}&\frac{27}{943}\end{bmatrix}\times\begin{bmatrix}1\\\
1\\\ 1\\\ 1\end{bmatrix},$ $\displaystyle=943\begin{bmatrix}\frac{133}{943}\\\
\frac{671}{943}\\\ \frac{739}{943}\\\
\frac{395}{943}\end{bmatrix}=\begin{bmatrix}133\\\ 671\\\ 739\\\
395\end{bmatrix}=[133].$

######  Proposition 4.3.2.

Fix $\gamma,n,\tilde{n}\in\mathbb{Z}_{>0}^{odd}$, and $N\in\mathbb{Z}_{>0}$.
Suppose both $n$ and $\tilde{n}$ start integral loops of length $N$. Let
$B,\tilde{B}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$ and $\tilde{n}$, respectfully. Let
$\rho,\tilde{\rho},\nu\text{ and }\tilde{\nu}$ be the count for the number of
zeros and ones for a single period of $B$ and $\tilde{B}$, respectfully.
Suppose further that $\nu=\tilde{\nu}$. Let $[n]$ and $[\tilde{n}]$ be the
associated integral loop vectors and $\mathcal{D}_{n}$ and
$\mathcal{D}_{\tilde{n}}$ constructed as by Equation (3.3). Then $[n]$ can be
transformed into $[\tilde{n}]$ by the following matrix:

$[\tilde{n}]=(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n].$
(4.6)

Moreover, this transformation is an element of the special linear group
$SL(\nu,\mathbb{R})$.

###### Proof.

The equality can be constructed directly from the second equation of
Proposition 4.3.1. Secondly, as
$\det(\mathcal{D}_{n}-3\mathbb{I}_{\nu})=(-1)^{\nu+1}(2^{\rho}-3^{\nu})$ and
$\det(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})^{-1}=(-1)^{\nu+1}(2^{\rho}-3^{\nu})^{-1}$
then their product has determinant one and belongs in $SL(\nu,\mathbb{R})$. ∎

######  Example 34.

Consider the integral loops induced by $n=23$, $\tilde{n}=19$, and
$\gamma=37$. Then we can transform [23] into [19] in the following manner:

$\begin{bmatrix}19\\\ 47\\\
89\end{bmatrix}=\begin{bmatrix}\frac{9}{37}&\frac{6}{37}&\frac{4}{37}\\\
\frac{32}{37}&\frac{9}{37}&\frac{6}{37}\\\
\frac{48}{37}&\frac{32}{37}&\frac{9}{37}\end{bmatrix}\begin{bmatrix}-3&2&0\\\
0&-3&4\\\ 8&0&-3\end{bmatrix}\begin{bmatrix}23\\\ 53\\\ 49\end{bmatrix}.$

Furthermore, we also observe that:

$\det\left(\begin{bmatrix}\frac{9}{37}&\frac{6}{37}&\frac{4}{37}\\\
\frac{32}{37}&\frac{9}{37}&\frac{6}{37}\\\
\frac{48}{37}&\frac{32}{37}&\frac{9}{37}\end{bmatrix}\begin{bmatrix}-3&2&0\\\
0&-3&4\\\
8&0&-3\end{bmatrix}\right)=\det\left(\begin{bmatrix}\frac{5}{37}&0&\frac{12}{37}\\\
\frac{-48}{37}&1&\frac{18}{37}\\\
\frac{-72}{37}&0&\frac{101}{37}\end{bmatrix}\right)=1.$

###  4.4 A Segue Into The One Row Sum Group

######  Proposition 4.4.1.

Fix $\gamma,n,\tilde{n}\in\mathbb{Z}_{>0}^{odd}$, and $N\in\mathbb{Z}_{>0}$.
Suppose both $n$ and $\tilde{n}$ start integral loops of length $N$. Let
$B,\tilde{B}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$ and $\tilde{n}$, respectfully. Let
$\rho,\tilde{\rho},\nu\text{ and }\tilde{\nu}$ be the count for the number of
zeros and ones for a single period of $B$ and $\tilde{B}$, respectfully.
Suppose further that $\nu=\tilde{\nu}$. Let $[n]$ and $[\tilde{n}]$ be the
associated integral loop vectors of $n$ and $\tilde{n}$ and $\mathcal{M}_{n}$
and $\mathcal{M}_{\tilde{n}}$ constructed as by Equation (3.5). Suppose
$\mathcal{M}_{n}$ is invertible over $\mathbb{C}$. Then $[n]$ can be
transformed into $[\tilde{n}]$ by the following matrix:

$[\tilde{n}]=\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}[n].$ (4.7)

###### Proof.

Equation (4.7) can be derived immediately from Equation (3.6). ∎

######  Example 35.

Consider the integral loop induced by $n=133$, $\tilde{n}=65$, and
$\gamma=943$. Then we can transform [133] into [65] in the following manner:

$\begin{bmatrix}65\\\ 569\\\ 1325\\\
2459\end{bmatrix}=\begin{bmatrix}1&2&4&8\\\ 1&2&4&512\\\ 1&2&256&512\\\
1&128&256&512\end{bmatrix}\begin{bmatrix}\frac{64}{51}&\frac{-2}{17}&\frac{-1}{51}&\frac{-2}{17}\\\
\frac{-1}{17}&\frac{-1}{204}&\frac{-1}{68}&\frac{4}{51}\\\
\frac{1}{408}&\frac{-1}{272}&\frac{1}{102}&\frac{-1}{272}\\\
\frac{-1}{544}&\frac{1}{408}&\frac{-1}{2176}&\frac{-1}{6528}\end{bmatrix}\begin{bmatrix}133\\\
671\\\ 739\\\ 395\end{bmatrix}.$

######  Lemma 4.4.2.

Fix $\gamma\in\mathbb{Z}_{>0}^{odd}$, $n\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose further that $n$ starts an integral loop of
length $N$. Let $B\in\\{0,1\\}^{**}$ such that
$B=(\chi_{\gamma}^{i}(n))_{i\geq 0}$. Let $\rho$ and $\nu$ be the count of the
number of zeros and ones in a single period of $B$. Let $[n]$ be the
associated integral loop vector. Let the matrix $\mathcal{M}_{n}$ given by
Equation (3.5) and assume that $\mathcal{M}_{n}$ is invertible over
$\mathbb{C}$. Then the first row of $\mathcal{M}_{n}^{-1}$ sums to one, while
the remaining rows sum to zero.

###### Proof.

Recall that the first row of $\mathcal{M}_{n}$ is the all ones vector
$\overrightarrow{\mathfrak{1}}^{\nu}$. By virtue of invertibility, we require
$\mathcal{M}_{n}^{-1}\mathcal{M}_{n}=\mathbb{I}_{\nu}$. This is only satisfied
if $\mathcal{M}_{n}^{-1}\overrightarrow{\mathfrak{1}}^{\nu}=e_{1}$. ∎

######  Theorem 4.4.3.

Let $\gamma,n,\tilde{n}\in\mathbb{Z}_{>0}^{odd}$, and $N\in\mathbb{Z}_{>0}$ be
given. Suppose both $n$ and $\tilde{n}$ start integral loops of length $N$.
Let $B,\tilde{B}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$ and $\tilde{n}$, respectfully. Let
$\rho,\tilde{\rho},\nu\text{ and }\tilde{\nu}$ be the count for the number of
zeros and ones for a single period of $B$ and $\tilde{B}$, respectfully.
Suppose further that $\nu=\tilde{\nu}$. Let $\mathcal{M}_{n}$ and
$\mathcal{M}_{\tilde{n}}$ be constructed as by Equation (3.5), and assume that
$\mathcal{M}_{n}$ is invertible over $\mathbb{C}$. Then each of the row sums
of $\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}$ is one.

###### Proof.

Recall that from Lemma 4.4.2 that the the first row sum of
$\mathcal{M}_{n}^{-1}$ is one, while the remaining row sums are zero. With a
proper change of variables, we can rewrite $\mathcal{M}_{n}^{-1}$ in the
following block diagram:

$\mathcal{M}_{n}^{-1}=\left[\begin{array}[]{c|ccc}1-\sum_{i=2}^{\nu}a_{1,i}&a_{1,2}&\cdots&a_{1,\nu}\\\
\hline\cr-\sum_{i=2}^{\nu}a_{2,i}&a_{2,2}&\cdots&a_{2,\nu}\\\
\vdots&\vdots&\ddots&\vdots\\\
-\sum_{i=2}^{\nu}a_{\nu,i}&a_{\nu,2}&\cdots&a_{\nu,\nu}\end{array}\right]$

Without loss of generality, let us consider the $j$th row of the product of
$\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}$. Written out explicitly, we find
that:

$\displaystyle{}[\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}]_{j}$
$\displaystyle=\left(1-\sum_{i=2}^{\nu}a_{1,i}-2^{m^{\prime}_{j}}\sum_{i=2}^{\nu}a_{2,i}-2^{m^{\prime}_{j}+m^{\prime}_{j+1}}\sum_{i=2}^{\nu}a_{3,i}-...\right)e_{j,1},$
$\displaystyle=\left(a_{1,2}+2^{m^{\prime}_{j}}a_{2,2}+2^{m^{\prime}_{j}+m^{\prime}_{j+1}}a_{3,2}+...\right)e_{j,2},$
$\displaystyle=\left(a_{1,3}+2^{m^{\prime}_{j}}a_{2,3}+2^{m^{\prime}_{j}+m^{\prime}_{j+1}}a_{3,3}+...\right)e_{j,3},$
$\displaystyle...$
$\displaystyle=\left(a_{1,\nu}+2^{m^{\prime}_{j}}a_{2,\nu}+2^{m^{\prime}_{j}+m^{\prime}_{j+1}}a_{3,\nu}+...\right)e_{j,\nu}.$

As a row sum, every negative term in $e_{j,1}$ cancels identically with a
corresponding term further down the row. Since the row choice was arbitrary,
we conclude that the row sums of the matrix product
$\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}$ are all ones. ∎

######  Example 36.

Consider the integral loops induced by $n=133$, $\tilde{n}=65$, and
$\gamma=943$. We can observe the row-sum property below:

$\displaystyle\mathcal{M}_{65}\mathcal{M}_{133}^{-1}\overrightarrow{\mathfrak{1}}^{4}$
$\displaystyle=\begin{bmatrix}1&2&4&8\\\ 1&2&4&512\\\ 1&2&256&512\\\
1&128&256&512\end{bmatrix}\begin{bmatrix}\frac{64}{51}&\frac{-2}{17}&\frac{-1}{51}&\frac{-2}{17}\\\
\frac{-1}{17}&\frac{-1}{204}&\frac{-1}{68}&\frac{4}{51}\\\
\frac{1}{408}&\frac{-1}{272}&\frac{1}{102}&\frac{-1}{272}\\\
\frac{-1}{544}&\frac{1}{408}&\frac{-1}{2176}&\frac{-1}{6528}\end{bmatrix}\begin{bmatrix}1\\\
1\\\ 1\\\ 1\end{bmatrix},$
$\displaystyle=\begin{bmatrix}\frac{227}{204}&\frac{-25}{204}&\frac{-11}{816}&\frac{19}{816}\\\
\frac{19}{102}&\frac{227}{204}&\frac{-25}{102}&\frac{-11}{204}\\\
\frac{-22}{51}&\frac{19}{102}&\frac{227}{102}&\frac{-50}{51}\\\
\frac{-400}{51}&\frac{-22}{51}&\frac{19}{51}&\frac{454}{51}\end{bmatrix}\begin{bmatrix}1\\\
1\\\ 1\\\ 1\end{bmatrix}=\begin{bmatrix}1\\\ 1\\\ 1\\\ 1\end{bmatrix}.$

Theorem 4.4.3 indicates a property of Equation (4.7) that deserves its own
attention. Thus we proceed with the following.

######  Definition 4.4.1.

A stochastic matrix over a field $F$ is a square matrix with entries from $F$
with the property that the entries in each of its columns add up to one[24].

Recall Theorem 4.4.3 only assumed that $\mathcal{M}_{n}$ was invertible.
However, if we suppose that $\mathcal{M}_{\tilde{n}}$ is also invertible, then
their product $\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}$ is invertible.
This takes us to another definition.

######  Definition 4.4.2.

The group of nonsingular stochastic $n\times n$ matrices over a field $F$ is
called the stochastic group of $n\times n$ matrices over $F$ and is denoted
$S(n,F)$[24].

Thus we see that in the case of Theorem 4.4.3, if
$\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}$ is nonsingular then
$\left(\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}\right)^{T}$ is an element
of $S(\nu,\mathbb{R})$. We provide one more property of this group, which will
be useful later. Recall that $Aff(n,F)$ is the $n\times n$ affine group over a
field $F$.

###  4.5 A Segue Into an Eigenvector Problem

Equation (4.6) and Equation (4.7) both provide a limited means to transform
one integral loop vector into another integral loop vector. So long as the
respective assumptions hold, it is clear that both equations satisfy the
conditions of an equivalence relation. This is formalized in the following
proposition.

######  Proposition 4.5.1.

Fix $\gamma,n,\tilde{n},\tilde{\tilde{n}}\in\mathbb{Z}_{>0}^{odd}$, and
$N\in\mathbb{Z}_{>0}$. Suppose $n$, $\tilde{n}$, and $\tilde{\tilde{n}}$ start
integral loops of length $N$. Let $B,\tilde{B},\text{ and
}\tilde{\tilde{B}}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$, $\tilde{n}$, and $\tilde{\tilde{n}}$,
respectfully. Let
$\rho,\tilde{\rho},\tilde{\tilde{\rho}},\nu,\tilde{\nu}\text{ and
}\tilde{\tilde{\nu}}$ be the count for the number of zeros and ones for a
single period of $B$, $\tilde{B}$, and $\tilde{\tilde{B}}$, respectfully.
Suppose further that $\nu=\tilde{\nu}=\tilde{\tilde{\nu}}$. Let
$\mathcal{M}_{n},\mathcal{M}_{\tilde{n}},\text{ and
}\mathcal{M}_{\tilde{\tilde{n}}}$ be constructed as by Equation (3.5), and
assume that all three are invertible over $\mathbb{C}$. Let
$\mathcal{D}_{n},\mathcal{D}_{\tilde{n}},\text{ and
}\mathcal{D}_{\tilde{\tilde{n}}}$ be constructed as Equation (3.3). Then
Equation (4.6) and Equation (4.7) independently satisfy the conditions of an
equivalence relation.

###### Proof.

We will check the properties for both equations.

  1. 1.

Reflexivity: $[n]\sim[n]$

    1. (a)

$[n]=\mathcal{M}_{n}\mathcal{M}_{n}^{-1}[n]=\mathbb{I}_{\nu}[n]=[n].$

    2. (b)

$[n]=(\mathcal{D}_{n}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n]=\mathbb{I}_{\nu}[n]=[n].$

  2. 2.

Symmetry: $[n]\sim[\tilde{n}]\Leftrightarrow[\tilde{n}]\sim[n]$.

    1. (a)

$[n]=\mathcal{M}_{n}\mathcal{M}_{\tilde{n}}^{-1}[\tilde{n}]\Leftrightarrow[\tilde{n}]=\mathcal{M}_{\tilde{n}}\mathcal{M}_{n}^{-1}[n].$

    2. (b)

$[n]=(\mathcal{D}_{n}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})[n^{\prime}]\Leftrightarrow[\tilde{n}]=(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n].$

  3. 3.

Transitivity: $[n]\sim[\tilde{n}]$ and $[\tilde{n}]\sim[\tilde{\tilde{n}}]$
then $[n]\sim[\tilde{\tilde{n}}].$

    1. (a)

$[n]=\mathcal{M}_{n}\mathcal{M}_{\tilde{n}}^{-1}[\tilde{n}]$ and
$[\tilde{n}]=\mathcal{M}_{\tilde{n}}\mathcal{M}_{\tilde{\tilde{n}}}^{-1}[\tilde{\tilde{n}}]$
then
$[n]=\mathcal{M}_{n}\mathcal{M}_{\tilde{n}}^{-1}\mathcal{M}_{\tilde{n}}\mathcal{M}_{\tilde{\tilde{n}}}^{-1}[\tilde{\tilde{n}}]=\mathcal{M}_{n}\mathcal{M}_{\tilde{\tilde{n}}}^{-1}[\tilde{\tilde{n}}].$

    2. (b)

$[n]=(\mathcal{D}_{n}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})[\tilde{n}]$
and
$[\tilde{n}]=(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{\tilde{n}}}-3\mathbb{I}_{\nu})[\tilde{\tilde{n}}]$
then
$[n]=(\mathcal{D}_{n}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{\tilde{n}}}-3\mathbb{I}_{\nu})[\tilde{\tilde{n}}]=(\mathcal{D}_{n}-3\mathbb{I}_{\nu})^{-1}(\mathcal{D}_{\tilde{\tilde{n}}}-3\mathbb{I}_{\nu})[\tilde{\tilde{n}}].$

∎

Proposition 4.5.1 formalizes the structure of the transformation equations.
However, it has its limitations. If we were inclined to construct a closed
loop from an integral loop vector to itself, then by transitivity and
reflexivity, the transformation would reduce to the identity. However, if we
were to take a combination of Equations (4.6) and (4.7), this is no longer the
case. This is described in the following theorem.

######  Theorem 4.5.2.

Fix $\gamma,n,\tilde{n}\in\mathbb{Z}_{>0}^{odd}$, and $N\in\mathbb{Z}_{>0}$.
Suppose both $n$ and $\tilde{n}$ start integral loops of length $N$. Let
$B,\tilde{B}\in\\{0,1\\}^{**}$ be the binary sequences associated to the
characteristic trajectories of $n$ and $\tilde{n}$, respectfully. Let
$\rho,\tilde{\rho},\nu\text{ and }\tilde{\nu}$ be the count for the number of
zeros and ones for a single period of $B$ and $\tilde{B}$, respectfully.
Suppose further that $\nu=\tilde{\nu}$. Let $\mathcal{M}_{n},\text{ and
}\mathcal{M}_{\tilde{n}}$ be constructed as by Equation (3.5), and assume that
both are invertible over $\mathbb{C}$. Let $\mathcal{D}_{n}\text{ and
}\mathcal{D}_{\tilde{n}}$ be constructed as Equation (3.3). Then $[n]$,
$\mathcal{D}_{n}$, and $\mathcal{M}_{n}$ satisfy the following properties:

  1. 1.

$[n]=\left(\mathcal{D}_{n}-3\mathbb{I}_{\nu}\right)^{-1}\left(\mathcal{D}_{\tilde{n}}-3\mathbb{I}_{\nu}\right)M_{\tilde{n}}M_{n}^{-1}[n].$

  2. 2.

$[n]=\mathcal{M}_{n}\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{2^{\rho}-3^{\nu}}e_{j,j}\right)\left(\mathcal{D}_{n}-3\mathbb{I}_{\nu}\right)[n]=\mathcal{A}_{n}[n].$

  3. 3.

$\mathcal{P}\mathcal{A}_{n}\mathcal{P}^{-1}\in Aff(\nu-1,\mathbb{R}).$

  4. 4.

$\mathcal{P}[n]=\left(\mathcal{P}\mathcal{A}_{n}\mathcal{P}^{-1}\right)\mathcal{P}[n].$

  5. 5.

$\mathcal{P}[n]$ is a fixed point of the affine transformation
$\mathcal{P}\mathcal{A}_{n}\mathcal{P}^{-1}.$

###### Proof.

Property (1) follows from the symmetry relations of Proposition 4.5.1.
Property (2) is derived from Proposition 4.3.1, Equation (4.5) combined with
Proposition 3.2.1 Equation (3.6). This is demonstrated below:

$\displaystyle\overrightarrow{\mathfrak{1}}^{\nu}$
$\displaystyle=\frac{1}{\gamma}(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n],$
$\displaystyle\left(\sum_{j=1}^{\nu}3^{\nu-j}e_{j,j}\right)\overrightarrow{\mathfrak{1}}^{\nu}$
$\displaystyle=\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{\gamma}e_{j,j}\right)(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n],$
$\displaystyle\overrightarrow{\mathfrak{3}}^{\nu}$
$\displaystyle=\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{\gamma}e_{j,j}\right)(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n],$
$\displaystyle\left(\frac{\gamma}{2^{\rho}-3^{\nu}}\mathcal{M}_{n}\right)\overrightarrow{\mathfrak{3}}^{\nu}$
$\displaystyle=\mathcal{M}_{n}\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{2^{\rho}-3^{\nu}}e_{j,j}\right)(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n],$
$\displaystyle[n]$
$\displaystyle=\mathcal{M}_{n}\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{2^{\rho}-3^{\nu}}e_{j,j}\right)(\mathcal{D}_{n}-3\mathbb{I}_{\nu})[n].$

The quantity in parenthesis is a diagonal matrix. It is the $\nu\times\nu$
analogue of $\overrightarrow{\mathfrak{3}}^{\nu}$ with descending powers of 3
along the main diagonal scaled by $1/(2^{\rho}-3^{\nu})$. Property (3) is
demonstrated in two steps. We claim first that $\mathcal{A}_{n}$ can be
written in the following block diagonal form:

$\mathcal{A}_{n}=\left[\begin{array}[]{c|ccc}1&0\times\mathfrak{1}_{\nu}^{T}\\\
\hline\cr b_{2}&a_{22}&\cdots&a_{2\nu}\\\ \vdots&\vdots&\ddots&\vdots\\\
b_{\nu}&a_{\nu 2}&\cdots&a_{\nu\nu}\end{array}\right].$ (4.8)

Then all that is required is a sequence of row and column transformations. We
choose such transformations that retain the same sequential order of terms of
the integral loop vector, though not in the same entries. This is readily
satisfied with conjugation by $\mathcal{P}$.

$\mathcal{P}\mathcal{A}_{n}\mathcal{P}^{-1}=\left[\begin{array}[]{ccc|c}a_{22}&\cdots&a_{2\nu}&b_{2}\\\
\vdots&\ddots&\vdots&\vdots\\\ a_{\nu 2}&\cdots&a_{\nu\nu}&b_{\nu}\\\
\hline\cr 0\times\mathfrak{1}_{\nu}^{T}&&&1\end{array}\right].$

With that established, we now need to prove that $\mathcal{A}_{n}$ has this
desired form. We compose the product leading to $\mathcal{A}_{n}$ from left to
right.

$\mathcal{M}_{n}\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{2^{\rho}-3^{\nu}}e_{j,j}\right)=\begin{bmatrix}\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{1}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{1}+m_{2}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{\nu}}}{2^{\rho}-3^{\nu}}\\\
\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{2}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{2}+m_{3}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{1}}}{2^{\rho}-3^{\nu}}\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{\nu}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{\nu}+m_{1}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{\nu-1}}}{2^{\rho}-3^{\nu}}\end{bmatrix}.$

We can observe that the row sums yield $[n]/\gamma$. Now composing with the
final matrix we have:

$\displaystyle M_{n}$
$\displaystyle\left(\sum_{j=1}^{\nu}\frac{3^{\nu-j}}{2^{\rho}-3^{\nu}}e_{j,j}\right)\left(D_{n}-3\mathbb{I}_{\nu}\right)$
$\displaystyle=\begin{bmatrix}\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{1}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{1}+m_{2}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{\nu}}}{2^{\rho}-3^{\nu}}\\\
\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{2}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{2}+m_{3}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{1}}}{2^{\rho}-3^{\nu}}\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\frac{3^{\nu-1}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-2}2^{m_{\nu}}}{2^{\rho}-3^{\nu}}&\frac{3^{\nu-3}2^{m_{\nu}+m_{1}}}{2^{\rho}-3^{\nu}}&...&\frac{2^{\rho-
m_{\nu-1}}}{2^{\rho}-3^{\nu}}\end{bmatrix}\begin{bmatrix}-3&2^{m_{1}}&0&\cdots&0&0\\\
0&-3&2^{m_{2}}&0&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
2^{m_{\nu}}&0&\cdots&\cdots&\cdots&-3\end{bmatrix}.$

Considering the first row, we find that we have the following sum:

$\displaystyle{}[\mathcal{A}_{n}]_{1}$
$\displaystyle=\left(\frac{-3^{\nu}+2^{\rho}}{2^{\rho}-3^{\nu}}\right)e_{1,1}+\left(\frac{3^{\nu-1}2^{m_{1}}-3^{\nu-1}2^{m_{1}}}{2^{\rho}-3^{\nu}}\right)e_{1,2},$
$\displaystyle+\left(\frac{3^{\nu-2}2^{m_{1}+m_{2}}-3^{\nu-2}2^{m_{1}+m_{2}}}{2^{\rho}-3^{\nu}}\right)e_{1,3}+...$
$\displaystyle=\frac{2^{\rho}-3^{\nu}}{2^{\rho}-3^{\nu}}e_{1,1}+0\times(e_{1,2}+...+e_{1,\nu})=e_{1,1}.$

Thus $\mathcal{A}_{n}$ has the desired form. Regarding Property (4) consider
Property (2),

$\displaystyle{}[n]$ $\displaystyle=\mathcal{A}_{n}[n],$
$\displaystyle\mathcal{P}[n]$ $\displaystyle=\mathcal{P}\mathcal{A}_{n}[n],$
$\displaystyle\mathcal{P}[n]$
$\displaystyle=\mathcal{P}\mathcal{A}_{n}\mathcal{P}^{-1}\mathcal{P}[n].$

Property (5) follows immediately.

∎

## Bibliography

  * [1] Ball-and-urn.
  * [2] S. Aaronson.  The busy beaver frontier.  SIGACT News, 51(3):32–54, sep 2020.
  * [3] J. Alves, M. Graça, M. Dias, and J. S. Ramos.  A linear algebra approach to the conjecture of Collatz.  Linear algebra and its applications, 394:277–289, 2005.
  * [4] R. A. Brualdi and M. H. A. Newman.  An enumeration problem for a congruence equation.  Journal of Research of the National Bureau of Standards, Section B: Mathematical Sciences, page 37, 1970.
  * [5] J. H. Conway.  Unpredictable iterations.  In The Ultimate Challenge: The 3x+1 Problem, pages 219–223. Amer. Math. Soc., 2010.
  * [6] H. Coxeter.  Cyclic sequences and frieze patterns.  In The Ultimate Challenge: The $3x+1$ Problem, pages 211–217. Amer. Math. Soc., 2010.
  * [7] P. J. Davis.  Circulant Matrices.  Wiley-Interscience, New York, NY, 1970.
  * [8] J. Dolan, A. Gilman, and S. Manickam.  A generalization of Everett’s result on the Collatz $3x+1$ problem.  Advances in Applied Mathematics, 8(4):405–409, 1987.
  * [9] C. Everett.  Iteration of the number-theoretic function $f(2n)=n$, $f(2n+1)=3n+2$.  Advances in Mathematics, 25(1):42–45, 1977.
  * [10] M. Gardner.  Mathematical games.  Scientific American, 226(6):114–121, 1972.
  * [11] H. Hasse.  Unsolved problems in elementary number theory.  Lectures at U. Maine (Orono), Spring 1975.
  * [12] A. S. (https://math.stackexchange.com/users/436618/angina seng).  Singular circulant matrix.  Mathematics Stack Exchange.  URL:https://math.stackexchange.com/q/3498906 (version: 2020-01-06).
  * [13] T. Hughes.  The vandermonde determinant, a novel proof, 2020.
  * [14] S. Kohl.  Wildness of iteration of certain residue-class-wise affine mappings.  Advances in Applied Mathematics, 39(3):322–328, 2007.
  * [15] A. Kontorovich and Y. Sinai.  Structure theorem for (d, g, h)-maps.  Bulletin of the Brazilian Mathematical Society, 33(2):213–224, July 2002.
  * [16] I. Korec.  A density estimate for the $3x+1$ problem.  Mathematica Slovaca, 44(1):85–89, 1994.
  * [17] J. Lagarias.  The $3x+1$ Problem and its generalizations.  American Mathematical Monthly, pages 3–23, 1985.
  * [18] J. Lagarias.  The $3x+1$ Problem: An overview.  In The Ultimate Challenge: The 3x+ 1 Problem, pages 3–29. Amer. Math. Soc., 2010.
  * [19] D. Lehmer.  Some properties of circulants.  Journal of Number Theory, 5(1):43–54, 1973.
  * [20] E. Lehtonen.  Two undecidable variants of collatz’s problems.  Theoretical Computer Science, 407(1):596–600, 2008.
  * [21] P. Michel.  Simulation of the collatz 3x+1 function by turing machines.  arXiv: Logic, 2014.
  * [22] P. Michel.  Problems in number theory from busy beaver competition.  Logical Methods in Computer Science, 11(4), dec 2015.
  * [23] P. Michel and M. Margenstern.  Generalized $3x+1$ functions and the theory of computation.  In The Ultimate Challenge: The 3x+1 Problem, pages 105–130. Amer. Math. Soc., 2010.
  * [24] D. G. Poole.  The stochastic group.  The American Mathematical Monthly, 102(9):798–801, 1995.
  * [25] D. A. Rawsthorne.  Imitation of an iteration.  Mathematics Magazine, 58(3):172–176, 1985.
  * [26] G. Sburlati.  On prime factors of determinants of circulant matrices.  Linear Algebra and its Applications, 432(1):100–106, 2010.
  * [27] T. Tao.  Almost all orbits of the collatz map attain almost bounded values, 2019\.
  * [28] H. Thomas.  The number of terms in the permanent and the determinant of a generic circulant matrix.  J. Algebraic Comb., 20(1):55?60, jul 2004.
  * [29] J. P. Van Bendegem.  The Collatz Conjecture. A case study in mathematical problem solving.  Logic and Logical Philosophy, 14(1):7–23, 2005.
  * [30] J. Whiteman.  In memoriam: Lothar Collatz.  International Journal for Numerical Methods in Engineering, 31(8):1475–1476, 1991.
  * [31] Yutsumura.  Determinant of a general circulant matrix, 2017.