# The shape of $x^{2}\bmod n$

Lee DeVille
Department of Mathematics, University of Illinois

###### Abstract

We examine the graphs generated by the map $x\mapsto x^{2}\bmod n$ for various
$n$, present some results on the structure of these graphs, and compute some
very cool examples.

##  1 Overview

For any $n$, we consider the map

$f_{n}(x):=x^{2}\bmod n.$

From this map, we can generate a (directed) graph $\mathcal{G}({n})$ whose
vertices are the set $\\{0,1,\dots,n-1\\}$ and edges from $x$ to $f_{n}(x)$
for each $x$. We show a few examples of such graphs later in the paper — one
particularly intruiging graph is shown in Figure 5, that appears as a subgraph
of $\mathcal{G}({10455})$. Figure 7, which shows the entire graph
$\mathcal{G}({817})$, is also excellent. As we can see from examples,
sometimes the graph $\mathcal{G}({n})$ is a forest (a collection of trees),
sometimes it has loops, etc. In this paper we will seek to characterize all
such graphs; not surprisingly, the shape of these graphs depend on the number
theoretic properties of the integer $n$.

We give a quick summary of the results below:

  1. 1.

(Theorem 2.1.3) We show that if $n=a\cdot b$ where $\gcd(a,b)=1$, then the
graph $\mathcal{G}({n})$ is the Kronecker product of the graphs
$\mathcal{G}({a})$ and $\mathcal{G}({b})$ (we define the Kronecker product in
Definition 2.1.1 below). Using induction, we can therefore determine the graph
$\mathcal{G}({n})$ in terms of its prime decomposition, and all that remains
is to describe $\mathcal{G}({p^{k}})$ for all primes $p$ and $k\geq 1$. We
break this up into several cases.

  2. 2.

(Theorem 2.2.5) Let $p$ be an odd prime. Let us denote by
$\mathcal{U}({p^{k}})$ the set of numbers that are relatively prime to
$p^{k}$; these are the multiplicative units modulo $p^{k}$. We use heavily the
fact that the units under multiplication modulo $p^{k}$ form a cyclic group,
and this allows us to characterize $\mathcal{U}({p^{k}})$ (we note here that
the technique for $\mathcal{U}({p^{k}})$ follows closely the results of [1]
where they studied $\mathcal{G}({p})$ for $p$ prime);

  3. 3.

(Theorem 2.3.4) Let $p$ be an odd prime. This theorem will fully characterize
$\mathcal{N}({p^{k}})$, the component of $\mathcal{G}({p^{k}})$ that
corresponds to the nilpotent elements.

  4. 4.

(Section 2.4) Finally, we work on the graph for $\mathcal{G}({2^{k}})$,
describing both $\mathcal{U}({2^{k}})$ and $\mathcal{N}({2^{k}})$ separately.

From this, we can characterize any $\mathcal{G}({n})$, and we then use this
characterization to compute several quantities of interest and work out many
sweet examples.

A few notes: this manuscript does not contain any new theoretical results and,
in fact, only uses results from elementary number theory111Anyone familiar
with the author’s body of research would know that any number theory appearing
here is perforce extremely elementary. If the reader is so inclined, they can
think of this paper as an extended pedagogical example. In fact, the author
recently taught UIUC’s MATH 347 (our undergrad math major ”intro to proofs”
course) and found that the students responded pretty well to visualizing the
graphs of various functions that appear in a math course at this level
(functions modulo some integer being a key family of examples). The author
also made some videos with visualizations for the square function considered
here [2], and got intrigued by the patterns that appear. This led to the
current manuscript.

##  2 The main theory

###  2.0 Summary of results

As noted above, there are four main results, and the sections below address
each of these in order. After we have stated the theoretical results in this
section, this is sufficient to describe all $\mathcal{G}({n})$ — with the
caveat that in many cases there is still some work to do to compute
everything. We work out many concrete examples in Section 3.

###  2.1 Kronecker products and the Classical Remainder Theorem

In this section we show how the graphs $\mathcal{G}({a})$ and
$\mathcal{G}({b})$ “combine” to form the graph of $\mathcal{G}({ab})$, when
$a,b$ are relatively prime.

######  Definition 2.1.1.

Let $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ be two (directed) graphs.
Let us define $G_{1}\oblong G_{2}$, the Kronecker product of $G_{1}$ and
$G_{2}$, as follows: the vertex set of $G_{1}\oblong G_{2}$ is the Cartesian
product $V_{1}\times V_{2}$, and we say that

$(v_{1},w_{1})\to(v_{2},w_{2})\in G_{1}\oblong G_{2}\mbox{ iff }v_{1}\to
w_{1}\in G_{1}\mbox{ and }v_{2}\to w_{2}\in G_{2}.$

In particular, the edge exists for the pair iff there is an edge for the first
component of each and one for the second component of each.

######  Remark 2.1.2.

One motivation for calling this the Kronecker product is that the adjacency
matrix of $G_{1}\oblong G_{2}$ is the Kronecker matrix product of the
adjacency matrices of $G_{1}$ and $G_{2}$. This is also called the Cartesian
product of graphs by many authors. We also note that it is straightforward to
show that the Kronecker graph product is associative, and so we can define
$n$-ary Kronecker products unambiguously as well.

######  Theorem 2.1.3.

If $gcd(a,b)=1$, then

$\mathcal{G}({ab})\cong\mathcal{G}({a})\oblong\mathcal{G}({b}).$

Furthermore, If we write

$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{j}^{\alpha_{j}}$

as the prime factorization of $n$, then

$\mathcal{G}({n})\cong\bigbox_{i=1}^{j}\mathcal{G}({p_{i}^{\alpha_{i}}}),$

namely: the graph for $n$ is just the Kronecker product of the individual
graphs for each of the $p_{i}^{\alpha_{i}}$.

Perhaps surprisingly, the proof of Theorem 2.1.3 is more or less equivalent to
the Classical Remainder Theorem (see Lemma 2.1.4 below). The basic idea goes
as follows: if we consider the map $x\mapsto x^{2}\bmod{ab}$, then we can
naturally map this to a pair where we first consider the operation modulo $a$,
and then consider the operation modulo $b$. (In fact, we can do this for any
$a,b$, not just those that are relatively prime.) However, if $a,b$ are
relatively prime, then the CRT tells us that we can invert this process, and
this is what gives us the full isomorphism.

######  Lemma 2.1.4.

[Classical Remainder Theorem (CRT)] [3, §7.6] Given a set of coprime numbers
$n_{1},n_{2},\dots,n_{j}$, then for any integers $a_{1},\dots,a_{j}$, the
system

$x\equiv a_{1}\bmod n_{1},\quad x\equiv a_{2}\bmod n_{2},\quad\cdots,\quad
x\equiv a_{j}\bmod n_{j}$

has a solution. Moreover, any two such solutions are congruent modulo
$n_{1}\times n_{2}\times\cdots\times n_{j}$.

######  Remark 2.1.5.

An equivalent statement of the CRT is that the map

$\displaystyle\mathbb{Z}/{(n_{1}\times n_{2}\times\cdots\times
n_{j})}\mathbb{Z}$
$\displaystyle\to\mathbb{Z}/{n_{1}}\mathbb{Z}\times\mathbb{Z}/{n_{2}}\mathbb{Z}\times\cdots\times\mathbb{Z}/{n_{j}}\mathbb{Z},$
$\displaystyle x\bmod{(n_{1}\times n_{2}\times\cdots\times n_{j})}$
$\displaystyle\mapsto(x\bmod n_{1},x\bmod n_{2},\dots,x\bmod n_{j}),$

is a ring isomorphism, which is why it respects the squaring operation.

###### Proof of Theorem 2.1.3.

The first claim basically boils down to the interpretation of Remark 2.1.5.
Let us consider the map from the vertex set of $\mathcal{G}({ab})$ to the
vertex set of $\mathcal{G}({a})\oblong\mathcal{G}({b})$ given by
$x\bmod(ab)\mapsto(x\bmod a,x\bmod b)$. By the CRT, this is a bijection of the
vertex sets. Now, assume that there is an edge $x\to y$ in $\mathcal{G}({ab})$
— this will be true iff $x^{2}=y\bmod{(ab)}$. But then $x^{2}=y\bmod a$ and
$x^{2}=y\bmod b$, and therefore there is an edge $(x\bmod a,x\bmod
b)\to(y\bmod a,y\bmod b)$ in $\mathcal{G}({a})\oblong\mathcal{G}({b})$ as
well. Conversely, if there is an edge $(x\bmod a,x\bmod b)\to(y\bmod a,y\bmod
b)$ in $\mathcal{G}({a})\oblong\mathcal{G}({b})$, then by CRT we have
$x^{2}=y\bmod{(ab)}$, and there is an edge $x\to y$ in $\mathcal{G}({ab})$.
Finally, the second claim follows directly from the first using induction. ∎

###  2.2 The graph of units $\mathcal{U}({p^{k}})$ when $p$ is an odd prime

In this section, we determine how to compute the graph containing the “units”
modulo $p^{k}$ when $p$ is an odd prime. We start with a few definitions and
state the main result, and then break down how we prove it.

######  Definition 2.2.1.

The set of multiplicative units modulo $n$ (or, more simply, the units modulo
$n$) are those numbers in the set $\\{0,1,\dots,n-1\\}$ that are relatively
prime to $n$. This set is typically denoted
$(\mathbb{Z}/{n}\mathbb{Z})^{\times}$ and the function
$\varphi(n)=\left|{(\mathbb{Z}/{n}\mathbb{Z})^{\times}}\right|$ is called
Euler’s phi function (or totient function). In this paper we will denote by
$\mathcal{U}({p^{k}})$ the graph induced by $x\mapsto x^{2}\bmod{p^{k}}$ on
the set of units.

######  Definition 2.2.2.

Let $\gcd(d,k)=1$. We define the multiplicative order of $k$, modulo $d$,
denoted $\mathsf{ord}_{d}(k)$, as the smallest power $p$ such that
$k^{p}\equiv 1\bmod d$, or $d|(k^{p}-1)$.

######  Definition 2.2.3.

Here we define several special graphs that appear all over the place in
$\mathcal{U}({p^{k}})$:

  * •

The (directed) cycle graph of length $k$, denoted $C_{k}$, is a directed graph
with vertex set $\\{1,\dots,k\\}$ and arrows $v_{i}\to v_{i+1\bmod k}$. Note
that we also allow the cycle of length 2, given by the graph $1\to 2,2\to 1$,
and the directed cycle of length $1$, which is just a single vertex labelled 1
with a loop to itself.

  * •

A tree is a connected graph with no cycles. A rooted tree is a tree with a
distinguished vertex, called the root. A grounded tree is a rooted tree with
two properties: all edges flow towards the root (i.e. for any vertex in the
tree, there is a path from that vertex to the root), and the root has a loop
to itself.

  * •

The flower cycle of length $\alpha$ and flower type $T$, denoted
$C_{\alpha}(T)$, is the directed graph defined in the following manner. Take
$k$ copies of the grounded tree $T$, denoted $T_{1},\dots,T_{k}$. Remove the
loop at the root from each of these, and then replace it with an edge from the
root of tree $i$ to the root of tree $i+1\bmod\alpha$.

  * •

The regular grounded tree of width $w>1$ and $\ell>0$ layers (denoted
$T_{w}^{\ell}$) is a tree with $w^{\ell}$ vertices, described as follows:
start with a root vertex and a loop to itself, this forms layer 0. In layer 1,
there are $w-1$ vertices, each with an edge to the root. For any layer
$k<\ell$, and for any vertex in layer $k$, there are $w$ vertices in layer
$k+1$ that map to each vertex in layer $k$. Layer $\ell$ is given by leaves
that map to vertices in level $\ell-1$.

######  Remark 2.2.4.

A few remarks:

  * •

Another way to describe the flower cycle is that we start with a cycle, and
then we glue $k$ copies of the tree at each vertex in the cycle.

  * •

Note that the in-degree of every vertex in $T_{w}^{\ell}$ is either $w$ or 0.

  * •

The graph $C_{\alpha}(T_{w}^{\theta})$ appears often in the sequel (esp. with
$w=2$), and we give a colloquial description here: start with a cycle of
length $C_{\alpha}$, and then to each vertex in the cycle, “glue” a tree of
type $T_{w}^{\theta}$. In this picture, the nodes in the cycle itself are the
periodic points, and the trees coming off each node are the preperiodic points
that map into that particular orbit. See Figure 1 for a few examples.

Figure 1: Examples of $C_{6}(T_{2}^{2})$ and $C_{3}(T_{2}^{3})$ as defined in
Definition 2.2.3. Recall that the subscript gives the number of terms in the
cycle (or periodic orbit) of the graph, and the tree tells us what is “hanging
off” of each of those periodic vertices. In one case we have the grounded tree
of width two and depth two, and in the other width two and depth three. Trees
of width two show up ubiquitously below — in particular they are the only
trees we see in $\mathcal{U}({p^{k}})$ when $p$ is an odd prime.

######  Theorem 2.2.5.

[Structure of $\mathcal{U}({p^{k}})$] Let $p$ be an odd prime, and write
$m=\varphi(p^{k})$. Write $m=2^{\theta}\mu$ where $\mu$ is odd. (Note that
$\varphi(p^{k})$ is always even, so $\theta\geq 1$.) For each divisor $d$ of
$\mu$, take $\varphi(d)/\mathsf{ord}_{d}(2)$ disjoint copies of
$C_{\mathsf{ord}_{d}(2)}(T^{\theta}_{2})$, and $\mathcal{U}({p^{k}})$ is
isomorphic to the disjoint union of these cycles over the divisors $d$.

######  Remark 2.2.6.

Note that this implies that every vertex in $\mathcal{U}({p^{k}})$ has an in-
degree of two or zero (note that the trees attached to the cycles are always
of the form $T_{2}^{\theta}$).

To describe the result a bit more colloquially: we first compute
$m=\varphi(p^{k})$, and pull out all possible powers of $2$, until we obtain
the odd number $\mu$. From there, we enumerate all of the divisors $d$ of
$\mu$, and these $d$ determine all of the periodic orbits of
$\mathcal{U}({p^{k}})$. Then the number of powers of $2$ that we pulled out
gives us the full structure of the pre-periodic points attached to these
periodic orbits.

Onto the proof: we start with the following result that was proven by Gauss in
[4]:

######  Proposition 2.2.7.

If $n=p^{k}$, where $p$ is an odd prime, then
$(\mathbb{Z}/{p^{k}}\mathbb{Z})^{\times}$ is a cyclic group of order
$\varphi(p^{k})=p^{k}-p^{k-1}$.

The fact that this group is cyclic allows us to more or less completely
characterize the graph structure of $\mathcal{U}({p^{k}})$. We follow the
approach of [1] who completely characterized $\mathcal{G}({p})$ for $p$ prime
in the same way (in this section the novelty is that we are extending these
ideas to $p^{k}$, but since $(\mathbb{Z}/{p^{k}}\mathbb{Z})^{\times}$ is
cyclic the same idea goes through).

We first give a definition and a lemma:

######  Definition 2.2.8.

We define $\mathcal{A}_{{m}}$ as the graph whose vertices are the set
$\\{0,1,\dots,m-1\\}$ and edges given by $x\mapsto 2x\bmod m$.

######  Lemma 2.2.9.

Let $G$ be any cyclic group of order $m$ (where here we denote the group
operation as multiplication). Call one of its generators $g$. We can define a
function on $G$ by

$g^{\alpha}\mapsto g^{2\alpha},\quad\alpha=0,1,\dots,m-1.$

This function is conjugate to the map $(\mathbb{Z}/m\mathbb{Z},x\mapsto
2x\bmod m)$, and so has the same dynamical structure (periodic orbits, fixed
points, etc.) and its graph is isomorphic to $\mathcal{A}_{{m}}$.

###### Proof.

Let us define the maps
$\alpha\colon\mathbb{Z}/m\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}$ with $x\mapsto
2x\bmod m$, $\gamma\colon G\to G$ with $\gamma(g^{a})=g^{2a}$, and
$\kappa\colon\mathbb{Z}/m\mathbb{Z}\to G$ with $\kappa(a)=g^{a}$. Since $g$
generates $G$, the map $\kappa$ is invertible. We see that
$\gamma\circ\kappa=\kappa\circ\alpha$, so $\alpha$ and $\gamma$ are conjugate.
In particular, note that $\alpha(x)=x$ iff $\gamma(\kappa(x))=\kappa(x)$ and
moreover that $\alpha^{k}(x)=x$ iff $\gamma^{k}(\kappa(x))=\kappa(x)$, so that
there is a one-to-one correspondence between the fixed/periodic points of
$\alpha$ and $\gamma$. In particular this implies that the two functions have
isomorphic graphs. ∎

###### Proof of Theorem 2.2.5.

By Lemma 2.2.9, the graph $\mathcal{U}({p^{k}})$ is isomorphic to
$\mathcal{A}_{{\varphi(p^{k})}}$ and the result follows. ∎

Basically we just need to understand $\mathcal{A}_{{m}}$. Under addition, this
is a cyclic group of order $m$, with generator $1$. We stress here that we are
now moving to additive notation for simplicity, so here the identity is $0$
and the generator is $1$; when we convert this back to the multiplicative
group $\mathcal{U}({p^{k}})$ we will have an identity of $1$ and a generator
of $g$. Some standard results from group theory [3, §2.3] tell us that:

  1. 1.

For any $d$ dividing $m$, the set of all elements with (additive) order $d$ is
given by

$S_{d}=\\{j(m/d):j\mbox{ such that }\gcd(j,d)=1\\};$

  2. 2.

The set $S_{d}$ has $\varphi(d)$ elements;

  3. 3.

Since $\sum_{d|m}\varphi(d)=m$, these sets exhaust $\mathbb{Z}/m\mathbb{Z}$.

Let us first consider the case with $m$ odd:

######  Proposition 2.2.10.

Let $m$ be odd, and consider the map $f(x)=2x$ on $\mathbb{Z}/m\mathbb{Z}$.
Then this map has a unique fixed point at $x=0$, and all other elements are
periodic under this map. The map $f$ leaves each of the $S_{d}$ invariant, and
$S_{d}$ decomposes into a disjoint union of periodic orbits, each with period
$\mathsf{ord}_{d}(2)$. (Note that since $\left|{S_{d}}\right|=\varphi(d)$,
there will be exactly $\varphi(d)/\mathsf{ord}_{d}(2)$ such disjoint orbits
and note that $\mathsf{ord}_{d}(2)$ divides $\varphi(d)$ by Fermat’s Little
Theorem.)

###### Proof.

We can see by inspection that no point other than $x=0$ is fixed by the map.
Now note that since $\gcd(2,m)=1$, the map $x\mapsto 2x$ is invertible, and is
thus effectively a permutation. Therefore all points are periodic under
repeated application of this map.

To prove the second claim in the proposition, note that $S_{d}$ is the set of
points in $\mathbb{Z}/m\mathbb{Z}$ with additive order $d$, i.e. $x\in S_{d}$
iff $dx\equiv 0\bmod m$ and if $0<d^{\prime}<d$, $d^{\prime}x\not\equiv
0\pmod{m}$. This is invariant under the map $x\mapsto 2x$ since $m$ is odd: if
$d^{\prime}(2x)\equiv 0\bmod m$ then $d^{\prime}x\equiv 0\bmod m$, etc.

Let $x\in S_{d}$ with $f^{k}(x)=2^{k}x\equiv x$, and if $x\in S_{d}$ then
$x=j(d/m)$ for $\gcd(j,d)=1$. This means that we have

$(2^{k}-1)j\frac{m}{d}\equiv 0\bmod m,$

which is equivalent to saying that $(2^{k}-1)j/d\in\mathbb{Z}$. Since
$\gcd(j,d)=1$, this is true iff $d|(2^{k}-1)$.

The period of $x$ is the smallest $k$ for which $2^{k}x=x$, which is the
smallest $k$ for which $d|(2^{k}-1)$, and this is $\mathsf{ord}_{d}(2)$ by
definition. ∎

We are now able to understand the cyclic group for more general $m$.

######  Proposition 2.2.11.

Let $m=2^{\theta}\mu$ where $\mu$ is odd, and again consider the map
$f(x)=2x\bmod m$. Then the graph $\mathcal{A}_{{m}}$ consists of flower
cycles, specifically: replace every cycle of length $\alpha$ in
$\mathcal{A}_{{\mu}}$ with a copy of $C_{\alpha}(T_{2}^{\theta})$.

###### Proof.

We first consider the basin of attraction of $0$, which consists of the
multiples of $\mu$. (Note that $f^{\theta}(x)=2^{\theta}x\equiv 0\bmod m$ for
some $\theta$ iff $x$ is a multiple of $\mu$.) In fact, we can see that if
$x=2^{q}\nu\mu$ with $q<\theta$ and $\nu$ odd, then $x$ reaches 0 in exactly
$k-q$ iterations, each passing through higher orders of $2$. For example, all
of the odd multiples of $\mu$ will be in the top layer (there will be exactly
$2^{\theta-1}$ of these); the odd multiples of $2\mu$ will be in the next
layer (exactly $2^{\theta-2}$ of these), and so on. Note that every vertex in
this tree has in-degree 2 or 0: nothing maps to the odd numbers in the top
layer, but each subsequent number has two preimages: given an $x$ such that
$2y\equiv x\bmod m$, we also have $2(y+m/2)\equiv x\bmod m.$ So in general, we
have a tree of type $T_{2}^{\theta}$ with $0$ at the root, the point
$m/2=2^{\theta-1}\mu$ the single point in layer $1$, the points
$\\{1,3\\}\times 2^{\theta-2}\mu$ in layer two (each of which map to
$2^{\theta-1}\mu$), the points $\\{1,3,5,7\\}\times 2^{\theta-3}\mu$ in layer
three, etc. We will call this the “tree rooted at 0” below.

We now claim that for any periodic orbit that appears in
$\mathcal{A}_{{\mu}}$, there is a corresponding flower orbit in
$\mathcal{A}_{{m}}$. Consider any period $k$ orbit in
$\mathbb{Z}/{\mu}\mathbb{Z}$ with elements $x_{1},\dots,x_{k}$. By definition,
$x_{i+1}\equiv 2x_{i}\bmod\mu$ and $x_{1}=2x_{k}\bmod\mu$. Now let
$y_{i}=2^{\theta}x_{i}$ and note that gives a periodic orbit modulo $m$: if
$x_{i+1}-2x_{i}$ is a multiple of $\mu$, then
$y_{i+1}-2y_{i}=2^{\theta}(x_{i+1}-x_{i})$ is a multiple of $m=2^{\theta}\mu$.
Now pick any of the $y_{i}$. We know that there is at least one
$z\in\mathbb{Z}/m\mathbb{Z}$ that maps to $y_{i}$ (since it is part of a
periodic orbit). Therefore there is another, $z_{1}=z\pm n/2$ that maps to
$y_{i}$, and this corresponds to the $n/2$ vertex in the tree rooted at 0. If
$z$ is odd, then the tree terminates, but if it is even, there are two numbers
that map to $z_{1}$, namely $z_{1}/2$ and $z_{1}/2\pm n/2$. As we move up the
branches of this tree, each layer removes one power of two, and each vertex
has exactly two vertices mapping to it, until we reach the $\theta$’th layer.
Therefore there will be a $T_{2}^{\theta}$ attached to $y_{i}$ — and the same
argument applies to any of the elements in any of the periodic orbits, and we
are done.

∎

######  Corollary 2.2.12.

If $m=2^{k}$ for some power of $k$, then the graph $\mathcal{A}_{{m}}$ is a
tree with $k$ layers. The $k$th layer consists of the $2^{k-1}$ odd numbers,
the $k-1$st layer is those $2^{k-2}$ numbers that are two times an odd, etc.
In particular, the graph $\mathcal{A}_{{2^{k}}}$ is a $T_{2}^{k}$.

One direct corollary of this is that if $n$ is a Fermat prime, then the graph
$\mathcal{U}({n})$ is a tree.

###  2.3 The graph of nilpotent elements $\mathcal{N}({p^{k}})$ when $p$ is an
odd prime

Now we can attack the case of those elements that are not units when $p$ is an
odd prime.

######  Definition 2.3.1.

We say that $x$ is nilpotent modulo $n$ if there exists some power $a$ such
that $x^{a}\equiv\bmod n$.

It is easy to see that $x$ is nilponent modulo $p^{k}$ iff $p|x$. Also note
that if $x^{a}\equiv 0\bmod n$ then $x^{b}\equiv 0\bmod n$ for any $b>a$, and
in particular it is true for $b$ being some power of two, so we have:

######  Lemma 2.3.2.

$x$ is nilpotent modulo $p^{k}$ $\iff$ $p|x$ $\iff$ $f_{p^{k}}^{\alpha}(x)=0$
for some $\alpha>0$. In particular, this implies that $\mathcal{N}({p^{k}})$
is a (connected) tree.

Now that we have established that $\mathcal{N}({p^{k}})$ is a tree and we want
to determine its structure. It can actually have an interesting and complex
structure, especially when $k$ is large. Our main result is the following.

######  Definition 2.3.3.

Let $p$ be an odd prime. Fix
$\widehat{x}\in\mathcal{U}({p})=\\{1,2,\dots,p-1\\}$, and for each $\ell$ we
define the tree ${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$ recursively:

  1. 1.

If $\ell$ is odd: then ${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$ is just
a single node with no edges;

  2. 2.

If $\ell$ is even and $\widehat{x}$ has no preimages modulo $p$: then then
${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$ is just a single node with no
edges;

  3. 3.

If $\ell$ is even and $\widehat{x}$ has two preimages modulo $p$: denote these
preimages by $z_{1}$ and $z_{2}$, then
${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$ is a rooted tree with
$2p^{\ell/2}$ trees mapping into this root:

$p^{\ell/2}$ copies of ${\mathrm{Tree}}_{p}^{({\ell/2})}({z_{1}})$ and
$p^{\ell/2}$ copies of ${\mathrm{Tree}}_{p}^{({\ell/2})}({z_{2}})$.

(Note by Remark 2.2.6 that this exhausts all possible cases.)

######  Theorem 2.3.4.

The graph $\mathcal{N}({p^{k}})$ is a rooted tree with $0$ as the root and
$p^{k-1}$ vertices. The in-neighborhood of 0 is constructed as follows: for
any $k/2\leq\ell<k$ and for any $1\leq y\leq p^{k-\ell}$ with $\gcd(y,p)=1$,
attach a tree of type ${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{y}})$, where
$\widehat{y}=y\bmod p$, to 0. For any $x$ (where $x\bmod p=0$ and
$x\bmod{p^{k}}\neq 0$), write $x$ as the (unique) decomposition
$x=\widetilde{x}p^{\ell}$ with $\gcd(\widetilde{x},p)=1$, and the in-
neighborhood of $x$ is the tree
${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$, where
$\widehat{x}=\widetilde{x}\bmod p$.

######  Remark 2.3.5.

The descriptions given in Theorem 2.3.4 and Definition 2.3.3 are recursive and
not explicit — although it is relatively easy to use these descriptions to
compute $\mathcal{N}({p^{k}})$ when $k$ is not too large. We give an
equivalent, but more explicit, description below.

Theorem 2.3.4 basically follows from the following lemma:

######  Lemma 2.3.6.

Consider $n=p^{k}$, let $x=\widetilde{x}p^{\ell}$ (where $\ell<k$) and
consider the equation

$q^{2}=x\bmod{p^{k}}.$ (1)

Write $\widehat{x}$ as the element of $\\{1,2,\dots,p-1\\}$ that is congruent
to $\widetilde{x}$ modulo $p$. If $\ell$ is odd, or if $\ell$ is even and
$\widehat{x}$ is a leaf in $\mathcal{U}({p})$, then (1) has no solutions. If
there are two numbers $\widetilde{z}_{1},\widetilde{z}_{2}$ such that
$\widetilde{z}_{i}^{2}=\widehat{x}\bmod p$, then (1) has $2p^{\ell/2}$
solutions. Half of these ($p^{\ell/2}$ of them) are solutions of the form
$zp^{\ell/2}$ where $z\equiv z_{1}\bmod p$ and the other half are solutions of
the form $zp^{\ell/2}$ where $z\equiv z_{2}\bmod p$.

###### Proof.

Let us first consider the case where $\ell=2$ as a warm-up; the general case
is similar but has more details.

$\ell=2$. Let us write $x=\widetilde{x}p^{2}$, $y=\widetilde{y}p$, and assume
that $y^{2}=x\bmod{p^{k}}$. This tells us that

$\displaystyle\widetilde{y}^{2}p^{2}$
$\displaystyle\equiv\widetilde{x}p^{2}\bmod{p^{k}},$
$\displaystyle\widetilde{y}^{2}$
$\displaystyle\equiv\widetilde{x}\bmod{p^{k-2}}.$

Note that we have $1\leq\widetilde{x}<p^{k-2}$ and
$1\leq\widetilde{y}<p^{k-1}$ — this is the range of prefactors we can put in
front of each of those powers.

Let us write $\widehat{x}=\widetilde{x}\pmod{p}$ and
$\widehat{y}=\widetilde{y}\pmod{p}$. If we consider the last equation modulo
$p$, this implies $\widehat{y}^{2}\equiv\widehat{x}\bmod p$. This implies that
if $\widehat{x}$ has no preimages in $\mathcal{G}({p})$ then there is no
solution. Let us assume that $\widehat{x}$ has two preimages in
$\mathcal{G}({p})$, and pick one of them, say $z_{1}$. If we can show that
there are exactly $p$ solutions to the system of congruences

$\widetilde{y}^{2}\equiv\widetilde{x}\bmod{p^{k-2}},\quad\widetilde{y}\equiv
z_{1}\bmod p,$

then we have established the result of the theorem for $\ell=2$. Let us define
two sets:

$S_{x}:=\\{\widetilde{x}:1\leq\widetilde{x}<p^{k-2}\land\widetilde{x}\equiv\widehat{x}\bmod
p\\},\quad
S_{y}:=\\{\widetilde{y}:1\leq\widetilde{y}<p^{k-1}\land\widetilde{y}\equiv\widehat{y}\bmod
p\\}.$

We can see that $\left|{S_{x}}\right|=p^{k-3}$ and
$\left|{S_{y}}\right|=p^{k-2}$, and of course $pS_{y}$ maps into $p^{2}S_{x}$
under the squaring map. Thus each point in $S_{x}$ is hit an average of $p$
times, but we want to show that it is exactly $p$ times. Let us parameterize
$S_{y}$ by $\widetilde{y}=z_{1}+\beta p$, with $0\leq\beta<p^{k-2}$. We claim
that as we run through these $\beta$, the values of $S_{x}$ each get hit
exactly $p$ times. First note that if we replace $\beta$ with $\beta+p^{k-3}$,
then we get

$(z_{1}+(\beta+p^{k-3})p)^{2}\equiv(z_{1}+\beta p)^{2}\bmod p^{k-2},$

so we only need consider $0\leq\beta<p^{k-3}$. We claim that these $\beta$
give distinct values modulo $p^{k-2}$, and since there are $p^{k-3}$ of them,
they must cover the set $S_{x}$ — and then shifting the arguments by $p^{k-3}$
gives the same values, and this gives us $p$ copies. All we need to show now
is that every element of $S_{x}$ gets hit once as $\beta$ runs from $0$ to
$p^{k-3}-1$. We compute:

$\displaystyle(1+\beta p)^{2}$ $\displaystyle\equiv(1+\beta^{\prime}p)^{2}$
$\displaystyle\pmod{p^{k-2}}$ $\displaystyle 1+2\beta p+\beta^{2}p^{2}$
$\displaystyle\equiv 1+2\beta^{\prime}p+(\beta^{\prime})^{2}p^{2}$
$\displaystyle\pmod{p^{k-2}}$ $\displaystyle 2\beta+\beta^{2}p$
$\displaystyle\equiv 2\beta^{\prime}+(\beta^{\prime})^{2}p$
$\displaystyle\pmod{p^{k-3}},$ $\displaystyle
2(\beta-\beta^{\prime})+p(\beta^{2}-(\beta^{\prime})^{2})$
$\displaystyle\equiv 0$ $\displaystyle\pmod{p^{k-3}},$

so we nowneed to show that the map $2\xi+p\xi^{2}$ has only one root on
$\mathbb{Z}/{p^{k-3}}\mathbb{Z}$. If we assume that $2\xi+p\xi^{2}\equiv
0\mod{p^{k-3}}$, then by taking modulo $p$, this gives $2\xi\equiv 0\bmod p$,
and thus $\xi\equiv 0\bmod p$. From this we have $p\xi^{2}\equiv
0\bmod{p^{3}}$, thus the same for $2\xi$, thus for $\xi$, etc. From this we
get that only $\xi=0$ can solve this equation, and we are done.

General $\ell$. The argument is similar: writing $x=\widetilde{x}p^{\ell}$,
$y=\widetilde{y}p^{\ell/2}$, and that $y^{2}=x\bmod{p^{k}}$. This tells us
that

$\displaystyle\widetilde{y}^{2}p^{\ell}$
$\displaystyle\equiv\widetilde{x}p^{\ell}\bmod{p^{k}},$
$\displaystyle\widetilde{y}^{2}$
$\displaystyle\equiv\widetilde{x}\bmod{p^{k-\ell}}.$

Note that we now have $1\leq\widetilde{x}<p^{k-\ell}$ and
$1\leq\widetilde{y}<p^{k-\ell/2}$. Again assume that $\widehat{x}$ has
preimages in $\mathcal{G}({p})$ and call one $z_{1}$. We now show that there
are $p^{\ell/2}$ solutions to the system

$\widetilde{y}^{2}\equiv\widetilde{x}\bmod{p^{k-\ell}},\quad\widetilde{y}\equiv
z_{1}\bmod p.$

Here we parameterize $\widetilde{y}=z_{1}+\beta p$ with
$0\leq\beta<p^{k-\ell/2-1}$. We obtain the same repeating argument when adding
a multiple of $p^{k-\ell-1}$, and so we only need to consider
$0\leq\beta<p^{k-\ell-1}$. But this will repeat
$p^{(k-\ell/2-1)-(k-\ell-1)}=p^{\ell/2}$ times, so again we only need to show
that every target gets hit in the cycle. But then the rest of the argument
follows.

∎

###### Proof of Theorem 2.3.4.

The lemma does most of the work for us here. Note that implicit in the lemma
that for any $x$, if we write $x=\widetilde{x}p^{\ell}$, then the basin of
attraction of $x$ depends only on $\widehat{x}=\widetilde{x}\bmod p$. We can
go through the cases: if $\ell$ is odd, then $x$ has no preimages modulo
$p^{k}$ by the lemma, and so it is a leaf in $\mathcal{N}({p^{k}})$ — and
similarly for $\ell$ even but $\widehat{x}$ having no preimages modulo $p$.

Finally, for the neighborhood of 0: note that if $\ell\geq k/2$, then
$x^{2}\equiv 0\bmod p^{k}$. Thus any such point maps to 0 under squaring, and
the preimage of each of these points is a tree of type
${\mathrm{Tree}}_{p}^{({\ell})}({\widehat{x}})$. ∎

Again it is worth pointing out that Lemma 2.3.6 tells us that basically all
that matters is the mod $p$ value of the prefactor. We can now define a non-
recursive way to compute the trees defined in Definition 2.3.3. We now
describe an algorithm that will compute this tree exactly. We will state but
not prove the algorithm.

######  Definition 2.3.7.

For any $p$ prime, and $x\in\\{0,\dots,n-1\\}$, we define the unfurled
preimage of $x$ of depth $\zeta$, $Z_{p}({x},{\zeta})$, as a directed tree.
The vertices of $Z_{p}({x},{\zeta})$ are all sequences of the form
$(a_{1},\dots,a_{\eta})$ with $\eta\leq\zeta$ such that $a_{1}=x$ and
$a_{i-1}=a_{i}^{2}\bmod p$. The edges of $Z_{p}({x},{\zeta})$ are

$(a_{1},a_{2},\dots,a_{\eta-1},a_{\eta})\to(a_{1},a_{2},\dots,a_{\eta-1})$

######  Remark 2.3.8.

It is always true that $Z_{p}({x},{\zeta})$ forms a tree, since each edge
moves from a sequence to a strictly smaller sequence and thus cannot have
loops. (The construction above is sometimes referred to as the “universal
cover of the graph $\mathcal{U}({p})$ rooted at $x$”.

######  Proposition 2.3.9.

$Z_{p}({x},{\zeta})$ is always a tree with degree $2$. If $x$ is a transient
point $\bmod\ p,$ then $Z_{p}({x},{\zeta})$ is a regular $2$-tree. If $p$ is
prime, and $p-1=2^{\theta}\mu$ with $\mu$ odd, and $\zeta\leq\mu$, then
$Z_{p}({x},{\zeta})$ is a regular $2$-tree. Otherwise, it is not a regular
$2$-tree.

######  Example 2.3.10.

Assume that $p\equiv 3\bmod 4$, so that $p-1=2\mu$. Let us first compute
$Z_{p}({1},{\zeta})$. Note that $1$ has two preimages: $1$ and $-1$, so
$Z_{p}({1},{1})$ is a regular $2$-tree. Now, if we want to go to depth
$\zeta=2$, we see that $-1$ has no preimage, but $1$ again has two, so the
$-1$ note terminates, but the $1$ node bifurcates. Again, going to depth
$\zeta=3$, we again terminate at $-1$ and bifurcate at $1$. Depending on the
depth to which we want to unfurl this tree, we can continue as long as we’d
like. Also note that we are labeling each node by the last term in the
sequence defining the node, and not the whole sequence itself (it is useful to
think of just this last value, but of course the sequence is important in the
definition to give unique descriptors for each node). See Figure 2.

Now, consider any periodic $x$. We claim that $Z_{p}({x},{\zeta})$ will be
isomorphic to $Z_{p}({1},{\zeta})$. To see this, note that since $x$ is
periodic, it has two preimages: one is the periodic $y_{1}$ with $y_{1}\to x$,
and the other is the preperiodic $z_{1}$ with $z_{1}\to x$, so we get a
regular $2$-tree at depth 1. To go to depth $\zeta=2$, we have that $y_{1}$ is
periodic so it again bifurcates into the periodic $y_{2}$ and perperiodic
$z_{2}$, whereas $z_{1}$ is a leaf in $\mathcal{G}({p})$, so it does not.

$1$$-1$$1$$-1$$1$$-1$$1$$-1$$\cdots$ Figure 2: Unfurling the case where
$\theta=1$.

######  Definition 2.3.11 (Layered trees and expansions).

We say that $T$ is a layered tree with $L$ layers if $V(T)$ can be written as
the disjoint union of $V_{1},V_{2},\dots,V_{L}$ and every edge in the graph
goes from layer $k$ to layer $k-1$. (This is basically the directed version of
$L$-partite.) Note that a vertex in a layer-$L$ tree is a leaf iff it is in
layer $L$.

Given an $L$-layer tree $T$, and the integer vector ${\bf
a}=(a_{1},a_{2},a_{3},\dots,a_{L-1})$, we define $T^{({\bf a})},$ $T$ expanded
by ${\bf a}$, to be the following $L$-layer tree:

  1. 1.

Let $v\in V(T)$ be a vertex in the $\ell$-th layer. Then the $a_{1}\times
a_{2}\times\cdots\times a_{\ell-1}$ vectors of the form

$(v,(\alpha_{1},\alpha_{2},\dots,\alpha_{\ell})),1\leq\alpha_{i}\leq a_{i}$

are all in the $\ell$-th later of $V(T^{({\bf a})})$.

  2. 2.

We define the edges of $T^{({\bf a})}$ by

$(v,(\alpha_{1},\alpha_{2},\dots,\alpha_{\ell}))\to(w,(\alpha_{1},\dots,\alpha_{\ell-1}))\quad\iff\quad
v\to w\mbox{ in }T.$

######  Lemma 2.3.12.

Let $n=p^{k}$, and let $x=\widetilde{x}p^{\ell}$ for $\ell<k$, and
$\widehat{x}=\widetilde{x}\bmod p$. Write $\ell=2^{\zeta}\lambda$, where
$\lambda$ is odd. Define $Z_{p}({\widehat{x}},{\zeta})$ as in Definition 2.3.7
and expand this graph by
$(p^{\ell/2},p^{\ell/4},p^{\ell/8},\dots,p^{2\lambda},p^{\lambda})$. Then this
graph is isomorphic to the basin of attraction of $x$ in
$\mathcal{N}({p^{k}})$.

###  2.4 The graph $\mathcal{G}({2^{k}})$

We have dealt with all powers of odd primes above, but still need to deal with
$n=2^{k}$. This will be a bit different than what has gone before, both for
the units and the nilpotents, but it will be similar enough that we can reuse
some earlier ideas here. First, a preliminary result that we can prove pretty
simply.

######  Proposition 2.4.1.

Let $n=2^{k}$. Then $\mathcal{G}({2^{k}})$ has exactly two components — one
corresponding to $\mathcal{U}({2^{k}})$ and the other to
$\mathcal{N}({2^{k}})$, and they are both trees. (Equivalently, the graph
$\mathcal{G}({2^{k}})$ has exactly two fixed points: $0$ and $1$, and no
periodic points.)

###### Proof.

The proof of the claim for $\mathcal{N}({2^{k}})$ is similar to that for odd
primes. The nilpotent elements modulo $2^{k}$ are exactly the even numbers,
and when these are raised to a high enough power, they will be 0 modulo
$2^{k}$. Now we consider the units, which are the odd numbers. Let $x\equiv
1\bmod 2^{\ell}$ with $1\leq\ell<k$. Then $x^{2}=1+\alpha 2^{\ell}$, and

$x^{2}=(1+2\alpha 2^{\ell}+\alpha^{2}2^{2\ell})=1+\alpha
2^{\ell+1}+\alpha^{2}2^{2\ell}\equiv 1\pmod{2^{\ell}+1}.$

Since the power has increased, from this we see that any odd number will be 1
modulo $2^{k}$ in at most $k-1$ steps, and we are done. ∎

From this we just need to characterize each of the two trees. We consider
$\mathcal{U}({2^{k}})$ first. One complication here is that the units modulo
$2^{k}$ do not form a cyclic group under multiplication, but we get something
that is close enough to make it work:

######  Lemma 2.4.2.

[4] The powers of 3 modulo $2^{k}$ form a cyclic group of size $2^{k-2}$ under
multiplication. If we write $S_{k}$ as the set

$\\{3^{q}\bmod 2^{k}:0\leq q<2^{k-2}\\},$

then the units modulo $2^{k}$ (basically the odd numbers) can be written as
$S_{k}\cup-S_{k}$.

Using Lemma 2.4.2, we can characterize $\mathcal{U}({2^{k}})$:

######  Proposition 2.4.3.

The graph of $\mathcal{U}({2^{k}})$ is a tree constructed in the following
manner: Start with the tree $T_{2}^{k}$, and for every node that is not a
leaf, add two leaves directly mapping into it.

###### Proof.

Since $S_{k}$ forms a cyclic subgroup of the units of size $2^{k-2}$, the
graph of these numbers can be realized as $\mathcal{A}_{{2^{k-2}}}$, which by
Corollary 2.2.12 is $T_{2}^{k}$. Note that all of the other units are
negatives of powers of $3$, and under squaring the negative sign cancels. So,
for example, if $x\in\mathcal{U}({2^{k}})$ is such that $z_{1}^{2}\equiv
z_{2}^{2}\equiv x\bmod{2^{k}}$, then we also have
$(-z_{1})^{2}\equiv(-z_{2})^{2}\equiv x\bmod{2^{k}}$, so that $x$ now has in-
degree four. Moreover, if there is any leaf in the $\mathcal{A}_{{2^{k-2}}}$,
i.e. a number in $S_{k}$ that is not a square modulo $2^{k}$, then there can
be no number in $-S_{k}$ that squares to it, since the negative of that number
would be in $S_{k}$. Therefore if a number is a leaf in the original tree,
then it remains a leaf when we add in the $-S_{k}$ terms as well. ∎

See Figure 3 for an example with $n=2^{7}$. We can also describe the graph
$\mathcal{U}({2^{k}})$ intuitively as follows: Start with the node at $1$ and
add a loop; add three nodes: $2^{k}-1$ and $2^{k/2}-1$, which will be leaves,
and the node $2^{k/2}+1$, which will itself be a tree; to $2^{k/2}+1$, we add
four inputs: the leaves $2^{k/4}-1$ and $3\cdot 2^{k/4}-1$, and two trees:
$2^{k/4}+1$ and $3\cdot 2^{k/4}+1$, etc.

Figure 3: The graph $\mathcal{U}({128})$. Note that it is a graph of depth $5$
(because the cyclic subgraph generated by powers of $3$ is of order $32$, but
instead of being a $T_{2}^{5}$, we add two leaves to each non-left node. So
for example without the additional leaves, $65=2^{6}+1$ would have two
preimages: $33=2^{5}+1$ and $97=3\cdot 2^{5}+1$, which themselves are trees.
But we also have the two leaves $31=2^{5}-1$ and $95=3\cdot 2^{5}-1$ as well.
(And similarly for all of the other nodes.)

Now onto the nilpotent elements. This case is a bit more complex than the case
where $p$ is odd. The main problem here is that there is no statement
analogous to Lemma 2.3.6 — the main idea there is that the basin of attraction
of any point of the form $x=\widetilde{x}p^{\ell}$ depends only on the value
of $\widehat{x}=\widetilde{x}\bmod p$, whenever $p$ is odd. This is clearly
not true in the case where $p=2$, since this would mean that the basin of
attraction for all numbers of the form $\mbox{(odd)}*2^{\ell}$ would be the
same, but this cannot be true since some odd numbers have square roots modulo
$2^{k}$ and some do not (q.v. the discussion of units above). In particular,
when computing the basin of attraction of a point $x=\widetilde{x}p^{\ell}$,
we didn’t need to pay attention to the “ambient space” $p^{k}$, but
unfortunately this breaks when $p=2$. So in theory one can compute this tree
for any given $n$, but we don’t expect such a nice result as seen in Theorem
2.3.4 or Lemma 2.3.12. We do have a partial result that we state without
proof.

######  Proposition 2.4.4.

Consider $n=2^{k}$, and let $x=\widetilde{x}2^{\ell}$, where
$\widetilde{x}\neq 1$. Let us define $\theta_{1},\theta_{2}$ by the equations

$\widetilde{x}-1=2^{\theta_{1}}\cdot q_{1},\quad\ell=2^{\theta_{2}}\cdot
q_{2},$

where $q_{1},q_{2}$ are odd. Define $\theta=\min(\theta_{1},\theta_{2})$.
Define $T_{2}^{\theta}$ as in Definition 2.3.3, add on the extra nodes as we
did in Proposition 2.4.3, and expand it as in Definition 2.3.11, where we
expand the first layer by $2^{\ell/2}$, the second layer by $2^{\ell/4}$, etc.
Then the basin of attraction of $x$ is isomorphic to this expanded graph.

##  3 Specific Computations

###  3.1 Computing the Kronecker products in practice

As we have seen above, the type of graph structures we see for primes, or
powers of primes, come in certain forms — and the graphs for composite $n$
come from Kronecker products of these. We have two main results in this
section: the first is that one can compute the Kronecker product “component by
component”, and the second one is a list of the typical graph products will we
see in practice.

######  Definition 3.1.1.

If $G$ are $H$ are two graphs with disjoint vertex sets, then we define the
disjoint union of $G$ and $H$, denote $G\oplus H$, as the graph with
$V(G\oplus H)=V(G)\cup V(H)$ and $E(G\oplus H)=E(G)\cup E(H)$.

Now, let us assume that there is a path from $(x_{1},y_{1})$ to
$(x_{2},y_{2})$ in $G\oblong H$. If we ignore the $y$’s, this gives a path
from $x_{1}$ to $x_{2}$ in $G$, and if we ignore the $x$’s, this gives a path
from $y_{1}$ to $y_{2}$ in $H$. Therefore if $(x_{1},y_{1})$ and
$(x_{2},y_{2})$ are in the same component of $G\oblong H$, then $x_{1}$ and
$x_{2}$ must be in the same component in $G$, and $y_{1}$ and $y_{2}$ must be
in the same component in $H$. This gives the following:

######  Proposition 3.1.2.

Let $G$ and $H$ be graphs, and let

$G=\bigoplus_{i\in I}G_{i},\quad\quad H=\bigoplus_{j\in J}H_{j}$

be the decomposition of each graph into its connected components. Then we have

$G\oblong H=\bigoplus_{i\in I,j\in J}(G_{i}\oblong H_{j}),$

where the individual terms in the union are themselves disjoint. More
specifically, if there is a path from $(x_{1},y_{1})$ to $(x_{2},y_{2})$ in
$G\oblong H$, then there must be a path from $x_{1}$ to $x_{2}$ in $G$ and one
from $y_{1}$ to $y_{2}$ in $H$.

Basically this means that we can compute the Kronecker product “component by
component” — more specifically, when computing the Kronecker product we can
just look at each component individually and not worry about the impact from
other components. This is good, because we can compartmentalize. However, one
caveat, as we will see below: it is possible for the product of two connected
graphs to not be connected, so that some of the $G_{i}\oblong H_{j}$ terms in
the expansion above might not themselves be a single components, but can be
multiple components. However, we do see that the number of connected
components of $G\oblong H$ is bounded below by the product of the numbers of
connected components of $G$ and $H$, respectively. Ok, so what do these
component-by-component products actually look like?

As we learned from Theorems 2.2.5 and 2.3.4, every component of
$\mathcal{G}({p^{k}})$ is either a flower cycle, or a looped tree (recall
Definition 2.2.3). This, with Proposition 3.1.2, tells us that the natural
question is what happens when we take the Kronecker product of two graphs
which are each of one of these two types. We categorize all of the cases we
might expect to see later in the following Proposition.

######  Proposition 3.1.3.

We have the following results:

  1. 1.

(Two looped trees) If $T_{1}$ and $T_{2}$ are looped trees, then so is
$T_{1}\oblong T_{2}$ — specifically, this implies that $T_{1}\oblong T_{2}$ is
connected, has a single root vertex, that root vertex loops to itself, and all
vertices flow toward that root.

  2. 2.

(Degrees) Assume that $T_{1}$ and $T_{2}$ are looped trees with the property
that every vertex in $T_{i}$ either has in-degree $w_{i}$ or $0$. Then every
vertex in $T_{1}\oblong T_{2}$ has in-degree $w_{1}\times w_{2}$ or $0$.

  3. 3.

(Specific grounded trees) For any widths $w_{1},w_{2}$ and depth $\theta$, we
have

$T_{w_{1}}^{\theta}\oblong T_{w_{2}}^{\theta}\cong T_{w_{1}\cdot
w_{2}}^{\theta}.$

(If we take two regular grounded trees of the same depth, then we get a
regular grounded tree of that depth, just wider.)

  4. 4.

(Another description of flower cycles)

$C_{\alpha}\oblong T\cong C_{\alpha}(T).$

  5. 5.

(One looped tree and one flower cycle)

$C_{\alpha}(T_{1})\oblong T_{2}\cong C_{\alpha}(T_{1}\oblong T_{2}).$

  6. 6.

(Two flower cycles) Let $G=C_{\alpha}(T_{1})$ and $H=C_{\beta}(T_{2})$. Let
$\gamma=\gcd(\alpha,\beta)$ and $\lambda=\operatorname{lcm}(\alpha,\beta)$.
Then $G\oblong H$ is $\gamma$ disjoint copies of the graph
$G_{\lambda}(T_{1}\oblong T_{2})$.

Note the last case where two connected graphs have a disconnected product!

###### Proof.

  1. 1.

Consider the vector $(0,0)$ in $V(T_{1})\times V(T_{2})$, where each $0$
corresponds to the root in that tree. Then note that $(0,0)\to(0,0)$ by
definition, and we have this loop. More generally, if we take any $(x,y)\in
V(T_{1})\times V(T_{2})$, then there is a finite path from $x$ to $0$ in
$T_{1}$ and a finite path from $y$ to $0$ in $T_{2}$, so there is a finite
path (whose length is the maximum of the two aforementioned paths) from
$(x,y)$ to $(0,0)$.

  2. 2.

In fact we prove something a bit more general: if $x\in V(G)$ has an in-degree
of $k$ and $y\in V(H)$ has an in-degree of $l$, then $(x,y)\in V(G\oblong H)$
has an in-degree of $k\times l$. To see this, note that if $z_{i}\to x$ for
$i=1,\dots,k$ and $w_{j}\to y$ for $j=1,\dots,l$, then $(z_{i},w_{j})\to(x,y)$
for all $i,j$. The claim follows directly.

  3. 3.

Let us consider the case where we have two trees $G_{1}=T_{w_{1}}^{\theta}$
and $G_{2}=T_{w_{2}}^{\theta}$. See Lemma 3.1.4 below for a parameterization
of each of these trees. Then, the root of $G_{1}\oblong G_{2}$ is $(0,0)$
where $0$ is the root of each $G_{1}$. Note that it has a loop to itself. Let
us define the first layer of $G_{1}\oblong G_{2}$ to be any pair
$(k_{1},k_{2})$ with $0\leq k_{1}\leq w_{1}-1$ $0\leq k_{2}\leq w_{2}-1$ but
not both zero. Note that all of these map to $(0,0)$ in one step, and there
are exactly $w_{1}w_{2}-1$ of these. Now we define the $\ell$th layer of
$G_{1}\oblong G_{2}$: given pair $(v_{1},v_{2})$ where $v_{1}$ is in level
$\ell_{1}$ of $G_{1}$ and $v_{2}$ is in level $\ell_{2}$ of $G_{2}$, define
$\ell=\max(\ell_{1},\ell_{2})$. Note that any such vertex will map down to
layer $\ell-1$. Moreover, if $\ell<\theta$, then each of these vertices has
exactly $w_{1}w_{2}$ preimages, because we can append $w_{1}$ numbers to the
end of $v_{1}$ and $w_{2}$ numbers to the end of $v_{2}$. If $\ell=\theta$,
then these elements are all leaves, and we are done.

  4. 4.

This is actually a bit trickier than it looks, since these two descriptions
are isomorphic but not equal. Recall the definition of $C_{\alpha}(T)$: we
define the vertices of this graph to be $(v,\beta)$ where $v\in V(T)$ and
$1\leq\beta\leq\alpha$. The edges in $C_{\alpha}(T)$ are defined as follows:

$(v,\beta)\to(w,\gamma)\iff(\beta=\gamma\land v\to
w)\lor(v=w=r\land\gamma=\beta+1).$

However, in $C_{\alpha}\oblong T$ (actually $T\oblong C_{\alpha}$ but who’s
counting) we have

$(v^{\prime},\beta^{\prime})\to(w^{\prime},\gamma^{\prime})\iff v^{\prime}\to
w^{\prime}\land\gamma^{\prime}=\beta^{\prime}+1.$

Now let us define a map $\psi\colon C_{\alpha}(T)\to C_{\alpha}\oblong T$ as
$\psi(v,\beta)=(v,\beta-\mathcal{L}(v))$, where $\mathcal{L}(v)$ is the level
of the vertex $v$ (in this case, the number of edges it takes to get from $v$
to $r$). Now, let us assume that $\varphi(v,\beta)\to\psi(w,\gamma)$ in
$C_{\alpha}\oblong T$. This is true iff
$(v,\beta-\mathcal{L}(v))\to(w,\gamma-\mathcal{L}(w))$ in $C_{\alpha}\oblong
T$, which if true iff $v\to w$ in $T$ and
$\gamma-\mathcal{L}(w)=\beta-\mathcal{L}(v)+1$. Now we claim that this is
equivalent to $(v,\beta)\to(w,\gamma)$ in $C_{\alpha}(T)$. Breaking up by
cases: if $v\neq w$, then $\mathcal{L}(w)=\mathcal{L}(v)=1$, which would imply
$\gamma=\beta$, and if $v=r$, then $w=r$, and
$\mathcal{L}(v)=\mathcal{L}(w)=0$, which would imply $\gamma=\beta+1$.

  5. 5.

This follows from the previous result twice and associativity, since

$C_{\alpha}(T_{1})\oblong T_{2}=(C_{\alpha}\oblong T_{1})\oblong
T_{2}=C_{\alpha}\oblong(T_{1}\oblong T_{2})=C_{\alpha}(T_{1}\oblong T_{2}).$

  6. 6.

Let us first note that if we consider two bare cycles, we get a similar
formula: Let $G_{1}=C_{\alpha}$ and $G_{2}=C_{\beta}$. Note that we can think
of these cycles as the map $x\mapsto x+1$ on $\mathbb{Z}/{\alpha}\mathbb{Z}$
and $\mathbb{Z}/{\beta}\mathbb{Z}$ respectively, and here $G_{1}\oblong G_{2}$
will be the graph of the map $(x_{1},x_{2})\mapsto(x_{1}+1,x_{2}+1)$ on
$\mathbb{Z}/{\alpha}\mathbb{Z}\times\mathbb{Z}/{\beta}\mathbb{Z}$. It is easy
enough to see that the element $(1,1)$ has order $\lambda$, and so every point
is on a periodic cycle of length $\lambda$. Since there are $\alpha\cdot\beta$
total vertices, and $\alpha\cdot\beta/\lambda=\gamma$, there are exactly
$\gamma$ distinct periodic cycles.

To get the full case: we have

$C_{\alpha}(T_{1})\oblong C_{\beta}(T_{2})=(C_{\alpha}\oblong
T_{1})\oblong(C_{\beta}\oblong T_{2})=(C_{\alpha}\oblong
C_{\beta})\oblong(T_{1}\oblong T_{2}),$

and we have computed above that $C_{\alpha}\oblong C_{\beta}$ is $\gamma$
copies of $C_{\lambda}$.

∎

######  Lemma 3.1.4.

We can parameterize $T_{w}^{\theta}$ as follows: let $V_{0}=\\{0\\}$, $V_{1}$
be the set $\\{1,\dots,w-1\\}$ and let

$V_{\ell}=\\{(v_{1},v_{2},\dots,v_{\ell}):1\leq v_{1}\leq w-1,\forall
k>1,1\leq v_{k}\leq w\\}.$

(These correspond to the “layers” in the graph, so any vertex in $V_{\ell}$ is
“in layer $\ell$”.) Let $V=\cup_{i=0}^{\theta}V_{\ell}$. Now define edges as
follows: for all $k\in V_{1}$, add an edge $k\to 0$, and for all $v\in
V_{\ell}$ with $2\leq\ell\leq\theta$, add the edge

$(v_{1},v_{2},\dots,v_{\ell-1},v_{\ell})\to(v_{1},v_{2},\dots,v_{\ell-1}),$

i.e. throw out the last component. Then this graph is isomorphic to
$T_{w}^{\theta}$.

###  3.2 The same unit graph can show up in many places

A natural question is how similar the graphs can be for different $n$.
However, note that if we have two primes $p,q$ with $p\neq q$, then
$\varphi(p)\neq\varphi(q)$, so they do not have isomorphic sets of units. But
it is possible that we can have two primes $p\neq q$ with
$\varphi(p^{k})=\varphi(q)$, and thus
$\mathcal{U}({p^{k}})\cong\mathcal{U}({q})$. For example, we have that

$\varphi(27)=\varphi(19)=18,$

so $\mathcal{U}({27})\cong\mathcal{U}({19})\cong\mathcal{A}_{{18}}$. We now
work both cases out. Since $18=2\cdot 9$, we have $\theta=1$ (so the flowers
on the cycle are just one node sticking out) and the divisors are $1,3,9$.
Since $\varphi(3)=\mathsf{ord}_{3}(2)=2$, there is one orbit of period $2$,
and since $\varphi(9)=\mathsf{ord}_{9}(2)=6$, there is one orbit of period
$6$. This determines the graph of units completely. For $n=19$, of course, we
have that $\mathcal{N}({19})$ is just $0$ with a loop to itself, but
$\mathcal{N}({27})$ is more complicated. The set of points that map to zero
modulo $27=3^{3}$ are the two points $9=3^{2}$ and $18=2\cdot 3^{2}$. If we
recall the graph $\mathcal{G}({3})$, we see that $1$ has a preimage of $2$,
and $2$ has no preimage. Therefore $18$ is a leaf in $\mathcal{N}({27})$,
whereas $9$ is a tree of the form ${\mathrm{Tree}}_{3}^{({2})}({1})$, which
will be a regular tree of width $6$ and depth $1$ (there are three trees of
type ${\mathrm{Tree}}_{3}^{({1})}({1})$ and three of type
${\mathrm{Tree}}_{3}^{({1})}({2})$, which are themselves single nodes by
definition, so are leaves in $\mathcal{N}({27})$). See Figure 4.

Figure 4: The graphs $\mathcal{G}({27})$ and $\mathcal{G}({19})$. Note that
they are isomorphic on the units (the graphs are the same, but of course the
values at the vertices are different), with only a different nilpotent tree.

###  3.3 Example where we really go to town on the Kronecker products

As we proved in Proposition 3.1.3, all of the components that show up in
$\mathcal{G}({n})$ are themselves Kronecker products of graphs that show up in
the factors of other graphs. So, let’s say, for example, we want to find an
$n$ that contains a copy of the graph

$T_{2}^{1}\oblong T_{2}^{2}\oblong T_{2}^{3}\oblong T_{2}^{4}.$

One way to obtain this is to find primes that contain such graphs, and then
multiply these together. We know that a $\mathcal{G}({p})$ for $p$ prime will
contain a $T_{2}^{\theta}$ iff $p-1$ is divisible by exactly $\theta$ powers
of $2$. For $\theta=1$, we can pick $p_{1}=3$, and for $\theta=2$ we can pick
$p_{2}=5$. For $\theta=3$ we cannot pick $2^{3}+1$, since it’s not prime, and
we don’t want to pick any even multiple of $8$, as we’ll get too many powers
of $2$. So we can pick $p_{3}=41$, and finally we can pick $p_{4}=17$. Of
course, $p_{1}$, $p_{2}$, and $p_{4}$ are relatively small since they are
Fermat primes, but we need to stretch a bit for $p_{3}$.

Now we know that the basin of attraction of $1$ in $\mathcal{G}({p_{i}})$ is
exactly $T_{2}^{i}$, for $i=1,2,3,4$. We have $p_{1}p_{2}p_{3}p_{4}=10455$,
and therefore the basin of attraction of $1$ in $\mathcal{G}({10455})$ is
exactly $T_{2}^{1}\oblong T_{2}^{2}\oblong T_{2}^{3}\oblong T_{2}^{4}$, shown
in Figure 5. (In fact, to generate this picture we actually just directly
computed the subgraph of $\mathcal{G}({10455})$ containing $1$ directly.) It’s
a pretty wild graph: it has a radius of $4$ due to the $T_{2}^{4}$ term, but
the smaller terms give it some interesting heterogeneity (e.g. each
intermediate node has leaves hanging off of it, etc.).

Figure 5: The graphs $T_{2}^{1}\oblong T_{2}^{2}\oblong T_{2}^{3}\oblong
T_{2}^{4}$, which appears as the basin of attraction of $1$ in the graph
$\mathcal{G}({10455})$. At this point, it is perhaps clear why we gave “flower
cycles” their names: the

In fact, we can completely understand the graph of $\mathcal{G}({10455})$
using the tools above. Note that since $p_{1},p_{2},p_{4}$ are all Fermat
primes, their graphs consist of a tree containing $p_{i}-1$ nodes, plus a $0$
with a loop, so is the union $T_{2}^{i}\cup T_{1}^{1}$. For $p_{3}=41$, we
note that $p-1=40=8*5$, and $\mathsf{ord}_{5}(2)=\varphi(5)=4$, so
$\mathcal{G}({41})$ has a single loop of period $4$ in the form of a
$C_{4}(T_{2}^{3})$, plus a $T_{2}^{3}$ going to $1$, plus the single loop at
$0$. There are 24 possible products in the expansion

$(T_{2}^{1}\cup T_{1}^{1})\oblong(T_{2}^{2}\cup
T_{1}^{1})\oblong(C_{4}(T_{2}^{3})\cup T_{2}^{3}\cup
T_{1}^{1})\oblong(T_{2}^{4}\cup T_{1}^{1})$

and notice that there is only one loop that can be chosen in any of these
products, so each product remains connected and there are precisely 24
components. Moreover, exactly eight of these will have a loop of period $4$,
and sixteen will not, for example for loops we can get a $C_{4}(T_{2}^{3})$ by
choosing $T_{1}^{1}\oblong T_{1}^{1}\oblong C_{4}(T_{2}^{3})\oblong
T_{1}^{1}$, but we can also get $C_{4}(T_{2}^{1}\oblong T_{2}^{3})$ by
choosing $T_{2}^{1}\oblong T_{1}^{1}\oblong C_{4}(T_{2}^{3})\oblong
T_{1}^{1}$, etc.

In general, we can extrapolate directly from this example that for any flower
cycle of the form $C_{\alpha}(T)$, where $T$ is a tree that can be formed by
taking Kronecker products of any collection of $T_{2}^{\theta}$’s, then we can
find a (square-free) $n$ that contains $C_{\alpha}(T)$.

###  3.4 Triggering divisors

######  Definition 3.4.1.

Given a period $k$, we say that $d$ is a triggering divisor for $k$ if

  * •

$\mathsf{ord}_{d}(2)=k$;

  * •

$\mathsf{ord}_{e}(2)\neq k$ for any $e$ that is a proper divisor of $d$.

######  Remark 3.4.2.

It follows directly from the definition that $\mathsf{ord}_{d}(2)=k$ iff $d$
is a multiple of a triggering divisor of $k$.

The name “triggering divisor” comes from the fact that the presence of such a
divisor of $m$ will trigger a periodic orbit of period $k$. (It might be that
other divisors of $m$ also give periodic orbits of period $k$, but this
minimal one is the one that triggers the condition…)

######  Corollary 3.4.3.

The graph $\mathcal{G}({p^{k}})$ has a flower orbit of type
$C_{k}(T_{2}^{\theta})$ iff $m=\varphi(p^{k})$ is a multiple of $2^{\theta}$
times a triggering divisor of $k$.

###### Proof.

This follows directly from Theorem 2.2.5 and the definition of triggering
divisor. ∎

We present the triggering divisors for all periods up to $50$ in Table 1, and
we have also put the first $n$ for which a period appears. Note that the
triggering divisors are not “unique” in some cases for certain periods — we
can obtain multiple numbers, neither of which divides the other. Also note,
interestingly, that these numbers might not even be relatively prime. In the
table, when there are multiple triggering divisors we have bolded the one that
gives rise to the first prime to have that period; for example, for period 18,
the smallest prime that is $1\pmod{19}$ is actually 191, whereas the smallest
prime that is $1\pmod{27}$ is 109.

Also, one might ask whether a composite number gives rise to a particular
periodic orbit before any prime does. In theory it is possible that one could
observe a (composite) period first in a composite number. For example, to
obtain a period-10 orbit, we can find a prime that gets it from a triggering
divisor (in this case, 47) or we could find a number with a period-2 and a
period-5 and multiply them. So, for example, $n=7*311=2177$ also has a
period-10 orbit, but $2177>47$. In practice we never found an example where a
period first shows up in a composite number but there are a lot of integers
that we didn’t check. The author is agnostic on the claim as to whether a
particular period length can ever show up first at a composite $n$.

There is a lot of heterogeneity in how large the triggering divisors are. One
thing that follows directly from the definitions is that

######  Proposition 3.4.4.

If $p$ is a Mersenne prime ($p$ is prime and $2^{p}-1$ is also prime) then
period-$p$ has the single triggering divisor $2^{p}-1$.

One can see this markedly at $2,3,5,7,13,17,19,31$ in Table 1, whereas for
primes that are not Mersenne primes (e.g. $p=11,37,39$ there is a “pretty
small” triggering divisor.)

The method to obtain the values in Table 1 was as follows. For any period $r$,
we list all divisors of the number $2^{r}-1$. For any $d$ that divides
$2^{r}-1$, we compute the multiplicative order of $2$ modulo $d$ and retain
those where $\mathsf{ord}_{d}(2)=r$. (Of course, since $d$ divides $2^{r}-1$,
then $\mathsf{ord}_{d}(2)$ must divide $r$, but it could be strictly smaller.)
From this retained list of divisors, we remove those divisors that are
multiples of others in the list. For example, let us consider period $6$. We
have $2^{6}-1=63$, the divisors of which are $1,3,7,9,21,63$. We have
$\mathsf{ord}_{1}(2)=1,\mathsf{ord}_{3}(2)=2$ and $\mathsf{ord}_{7}(2)=3$ and
remove those. Of the remaining three, we can compute that they satisfy
$\mathsf{ord}_{d}(2)=6$. But then notice that $63$ is a multiple of $9$ (and
also $21$ for that matter) so we throw out $63$, leaving $9$ and $21$. And
also note that these divisors are independent in the sense that they give
different sets of primes. For example, if we consider $p=19$, then
$19-1=18=2*9$, which is not divisible by $21$, and conversely $p=43$ has
$p-1=2*21$ which is not divisible by $9$. Note that $\theta=1$ in each of
these cases, so we see that $\mathcal{G}({19})$ has a single period-6 orbit of
type $C_{6}(T_{2}^{1})$ (since $\varphi(9)=6$) but $\mathcal{G}({43})$ has two
disjoint such orbits (since $\varphi(21)=12$). See Figure 6.

Period | Trig div | First | Period | Trig div | First
---|---|---|---|---|---
1 | 1 | 1 | 26 |  2731,24573 | 60083
2 | 3 | 7 | 27 | 262657 | 2626571
3 | 7 | 29 | 28 |  29,113,215,635 | 59
4 | 5 | 11 | 29 |  233,1103,2089 | 467
5 | 31 | 311 | 30 | 77,99,279,331,453,651,1661 | 199
6 |  9, 21 | 19 | 31 | 2147483647 | ??
7 | 127 | 509 | 32 | 65537 | 917519
8 | 17 | 103 | 33 |  161,623,599479 | 967
9 | 73 | 293 | 34 |  43691,393213 | 87383
10 |  11,93 | 23 | 35 |  71,3937,122921 | 569
11 |  23,89 | 47 | 36 |  37,95,109,135,247,351,365,949 | 149
12 |  13,35,45 | 53 | 37 |  223,616318177 | 2677
13 | 8191 | 376787 | 38 |  174763,1572861 | 699053
14 |  43,381 | 173 | 39 |  79,57337,121369 | 317
15 |  151,217 | 907 | 40 |  187,425,527,697,61681 | 1123
16 | 257 | 1543 | 41 |  13367,164511353 | 106937
17 | 131071 | 1572853 | 42 |  147,301,387,1011,1143,2667,5419,14491 | 883
18 | 19,27,219 | 109 | 43 |  431,9719,2099863 | 863
19 | 524287 | 8388593 | 44 |  115,397,445,2113,3415 | 461
20 | 25,41,55,155 | 83 | 45 |  631,2263,11023,23311 | 6311
21 |  49,337,889 | 197 | 46 |  141,535443,2796203 | 283
22 |  69,267,683 | 139 | 47 |  2351,4513,13264529 | 4703
23 |  47,178481 | 283 | 48 |  97,673,1799,2313,3341,61937 | 389
24 |  119,153,221,241 | 239 | 49 | 4432676798593 | ??
25 |  601,1801 | 3607 | 50 |  251,1803,4051,5403,6611,19811 | 503
Table 1: List of triggering divisors for period up to 50 Figure 6: The graphs
$\mathcal{G}({19})$ and $\mathcal{G}({43})$. Note that they both have period-6
orbits, and all periodic orbits have a “spoke” sticking out from the
$T_{2}^{1}$.

###  3.5 When cycles beget many more cycles

Consider the two numbers considered in the previous section: the primes $19$
and $43$. These numbers were chosen as primes that give period-6 orbits, but
“for different reasons”, because they derive from independent triggering
divisors. Since they both have periodic orbits of the same period, if we take
the Kronecker product, we will obtain many orbits of that period, from
Proposition 3.1.3, since $\alpha=\beta=\lambda=\gamma$ — so that the product
of two period-6 cycles is actually 6 distinct period-6 cycles.

Again, we first consider $\mathcal{G}({19})$. Since $19-1=18=2*9$, we need to
consider the divisors of $9$. We already saw that we have an orbit of period
$6$, and from the divisor $3$ we get and orbit of period $2$. Since $\theta=1$
we have $T_{2}^{1}$ attached to the graphs (just giving a “spoke”). Therefore
$\mathcal{G}({19})$ has four components, namely

$\mathcal{G}({19})\cong C_{6}(T_{2}^{1})\oplus C_{2}(T_{2}^{1})\oplus
T_{2}^{1}\oplus T_{1}^{1}.$

For $\mathcal{G}({43})$, we have $43-1=42=2*21$, and so we need to consider
the divisors $1,3,7,21$. As we computed above, the $d=21$ gives two period-6
orbits. Since $\varphi(7)=6$ and $\mathsf{ord}_{7}(2)=3$, the $d=7$ term gives
two period-3 orbits, and $d=3$ gives one period two orbit. Therefore
$\mathcal{G}({43})$ has 7 components:

$\mathcal{G}({43})\cong C_{6}(T_{2}^{1})\oplus C_{6}(T_{2}^{1})\oplus
C_{3}(T_{2}^{1})\oplus C_{3}(T_{2}^{1})\oplus C_{2}(T_{2}^{1})\oplus
T_{2}^{1}\oplus T_{1}^{1}.$

Now let us consider $n=817=19*43$. We know that the graph $\mathcal{G}({817})$
will contain at least $28$ components, since one of the graphs has 4 and the
other 7. But in fact, it will have many more components: each time we take the
product of two period-6 orbits, we actually get six period-6 orbits, etc.

For example, let us consider the $C_{6}(T_{2}^{1})$ component of
$\mathcal{G}({19})$, and multiply it against the seven components of
$\mathcal{G}({43})$. We get

$\displaystyle C_{6}(T_{2}^{1})\oblong C_{6}(T_{2}^{1})$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 6};$ $\displaystyle
C_{6}(T_{2}^{1})\oblong C_{3}(T_{2}^{1})$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 3};$ $\displaystyle
C_{6}(T_{2}^{1})\oblong C_{2}(T_{2}^{1})$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 2};$ $\displaystyle
C_{6}(T_{2}^{1})\oblong T_{2}^{1}$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 1};$ $\displaystyle
C_{6}(T_{2}^{1})\oblong T_{1}^{1}$ $\displaystyle=C_{6}(T_{2}^{1}).$

And also note that the first two components listed above each appear twice in
$\mathcal{G}({43})$, so when we multiply $C_{6}(T_{2}^{1})$ by the components
of $\mathcal{G}({43})$ we obtain $2*6+2*3+2+1=21$ copies of $C_{6}(T_{4}^{1})$
and one copy of $C_{6}(T_{2}^{1})$.

When we multiply the $C_{2}(T_{2}^{1})$ component of $\mathcal{G}({19})$
against the other seven, we obtain

$\displaystyle C_{2}(T_{2}^{1})\oblong C_{6}(T_{2}^{1})$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 2};$ $\displaystyle
C_{2}(T_{2}^{1})\oblong C_{3}(T_{2}^{1})$
$\displaystyle=C_{6}(T_{4}^{1})\quad\mbox{times 1};$ $\displaystyle
C_{2}(T_{2}^{1})\oblong C_{2}(T_{2}^{1})$
$\displaystyle=C_{2}(T_{4}^{1})\quad\mbox{times 2};$ $\displaystyle
C_{2}(T_{2}^{1})\oblong T_{2}^{1}$
$\displaystyle=C_{2}(T_{4}^{1})\quad\mbox{times 1};$ $\displaystyle
C_{2}(T_{2}^{1})\oblong T_{1}^{1}$ $\displaystyle=C_{2}(T_{2}^{1}).$

This gives a total of $2*2+2*1=6$ copies of $C_{6}(T_{4}^{1})$, one copy of
$C_{2}(T_{4}^{1})$, and one copy of $C_{2}(T_{2}^{1})$.

The other two components are simpler, since they are trees. Multiplying
$T_{2}^{1}$ against the components of $\mathcal{G}({43})$ gives $2$ copies of
$C_{6}(T_{4}^{1})$, $2$ copies of $C_{3}(T_{4}^{1})$, $1$ copy of
$C_{2}(T_{4}^{1})$, $1$ copy of $T_{4}^{1}$, and finally one copy of
$T_{2}^{1}$. Multiplying $T_{1}^{1}$ against these components just copies
them.

Putting this all together, we have

Graph type | copies
---|---
$C_{6}(T_{4}^{1})$ | 21 + 6 +2 = 29
$C_{3}(T_{4}^{1})$ | 2
$C_{2}(T_{4}^{1})$ | 1+1=2
$C_{6}(T_{2}^{1})$ | 1 + 1 +1 = 3
$C_{3}(T_{2}^{1})$ | 1 + 1 + 1 = 3
$C_{2}(T_{2}^{1})$ | 1 + 1 + 1 = 3
$T_{4}^{1}$ | 1
$T_{2}^{1}$ | 1+1=2
$T_{1}^{1}$ | 1

We can compare this against the graph given in Figure 7, which was obtained by
direct computation. Note that $C_{\alpha}(T_{4}^{1})$ will be a cycle of
period $\alpha$ with three leaves sticking out of each node, and
$C_{\alpha}(T_{2}^{1})$ will be a cycle of period $\alpha$ with a single stem
out of each node.

Figure 7: The (unlabeled) graph $\mathcal{G}({817})$, chosen because
$817=19*43$ (q.v. Figure 4)

###  3.6 When the nilpotents end up chillin’ in the corner

Consider $n=5^{4}=625$. Here we want to study the graph $\mathcal{G}({625})$,
and in particular, focus on $\mathcal{N}({625})$.

Let us use the formula in Theorem 2.3.4. We first compute the graph
${\mathrm{Tree}}_{5}^{({2})}({\widetilde{y}})$. Recalling the graph
$\mathcal{U}({5})$, we see that $1$ has two preimages: $1$ and $4$, and $4$
has two preimages: $2$ and $3$. In this case the actual values of the
preimages won’t be important, since
${\mathrm{Tree}}_{5}^{({1})}({\widetilde{y}})$ is a leaf regardless of
$\widetilde{y}$, due to the single power of $5$.

According to the theorem, ${\mathrm{Tree}}_{5}^{({2})}({1})$ has five incoming
copies of ${\mathrm{Tree}}_{5}^{({1})}({1})$ and five incoming copies of
${\mathrm{Tree}}_{5}^{({1})}({4})$, but these are all leaves, so
${\mathrm{Tree}}_{5}^{({2})}({1})$ is just a regular tree of width $10$, or
$T_{10}^{1}$. We get the same result for ${\mathrm{Tree}}_{5}^{({2})}({4})$.
And, of course,
${\mathrm{Tree}}_{5}^{({2})}({2})={\mathrm{Tree}}_{5}^{({2})}({3})$ is just a
single node.

We also have that ${\mathrm{Tree}}_{5}^{({3})}({\widetilde{y}})$ is a node
simply because $3$ is odd.

Now, the in-neighborhood of $0$ will be any numbers with 2 or 3 powers of $5$
in them. There are four such preimages with power three
(${\mathrm{Tree}}_{5}^{({3})}({\widetilde{y}})$ for $\widetilde{y}=1,2,3,4$,
which are all nodes) and $\varphi(25)=20$ such preimages of power two. As we
say above, half of these are trees $T_{10}^{1}$ and the other half are nodes.
Putting all of this together, the in-neighborhood of $0$ is $10$ copies of
$T_{10}^{1}$ and $14$ leaves. See Figure 8, where we have plotted
$\mathcal{N}({625})$ .

Figure 8: The graph $\mathcal{N}({625})$.

Note the structure is as we say: the node $0$ has fourteen leaves leading into
it: the four that come from $5^{3}$ terms: 125, 250, 375, 500, and the ten
that come from $5^{2}$ terms, where the prefactor is $2$ or $3$ modulo 5:
$25*\\{2,3,7,8,12,13,17,18,22,23\\}$. We also see that there are ten trees
that go into $0$, coming from $5^{2}$ terms, where the prefactor is $1$ or $4$
modulo 5: $25*\\{1,4,6,9,11,14,16,19,21,24\\}$.

Of course, if we want to understand the full graph $\mathcal{G}({625})$ we
also need to consider the units. Note that
$\varphi(625)=625-125=500=2^{2}*125$. The divisors are $1,5,25,125$, where we
have $\varphi(125)=\mathsf{ord}_{125}(2)=100$, so one period-100 orbit,
$\varphi(25)=\mathsf{ord}_{25}(2)=20$, so one period-20 orbit,
$\varphi(5)=\mathsf{ord}_{5}(2)=4$, so one period-4 orbit, and of course one
fixed point. Since $\theta=2$ these are all decorated with copies of
$T_{2}^{2}$, so in fact we have

$\mathcal{U}({625})=C_{100}(T_{2}^{2})\oplus C_{20}(T_{2}^{2})\oplus
C_{4}(T_{2}^{2})\oplus T_{2}^{2},$

so $\mathcal{G}({625})$ has five components, see Figure 9. (We can see that
the tree $\mathcal{N}({625})$ is just chilling down there in the corner.)

Figure 9: The graph $\mathcal{G}({625})$.

###  3.7 Well, *these* nilpotents ain’t messing around

Here we are going to describe the graph $\mathcal{G}({n})$ when
$n=177147=3^{11}$.

First we consider $\mathcal{U}({3^{11}})$. We have $\varphi(3^{11})=2\cdot
3^{10}$, so we have $\theta=1$ and $\mu=3^{10}$. The divisors $d$ of $3^{10}$
are, of course, $3^{k}$ for $k=0,1,\dots,10$. In each of these cases, it turns
out that $\varphi(3^{k})=\mathsf{ord}_{3^{k}}(2)=2\cdot 3^{k-1}$, so we have
exactly 11 periodic orbits: a fixed point, one of period 2, one of period 6,
etc. all the way up to one of period $2\cdot 3^{9}=39366$. Since $\theta=1$,
all of these periodic orbits have a “spoke” coming out of each periodic point.

Now for $\mathcal{N}({3^{11}})$. Let us first consider the neighborhood of
$0$: any $x$ of the form $x=\widetilde{x}p^{\ell}$ with $\ell\geq 6$ will map
directly into 0. If $\ell$ is odd, then these are leaves. If $\ell$ is even
but $\widetilde{x}\equiv 2\bmod 3$, then this is also a leaf. In the other
cases, we will have some more complex trees. For each even $\ell$, if
$\widetilde{x}$ is $1\pmod{3}$ we have a tree of type
${\mathrm{Tree}}_{3}^{({\ell})}({1})$, giving a total of
$1/2\varphi(3^{11-k})=3^{10-k}$ of them, and if $\widetilde{x}$ is $2\pmod{3}$
it is a leaf, so we have $1/2\varphi(3^{11-k})=3^{10-k}$ leaves. If $\ell$ is
odd we have $phi(3^{11-k})=2\cdot 3^{10-k}$ leaves. Therefore the total number
of leaves is $1+6+9+54+81=151$.

From here we see that we should have attached to $0$:

Tree type | ${\mathrm{Tree}}_{3}^{({10})}({1})$ | ${\mathrm{Tree}}_{3}^{({8})}({1})$ | ${\mathrm{Tree}}_{3}^{({6})}({1})$ | leaves
---|---|---|---|---
Count | 1 | 9 | 81 | 151
Table 2: The structures directly adjacent to $0$ in the graph
$\mathcal{N}({3^{11}})$

Moreover, we can see that since $10=2\cdot 5$,
${\mathrm{Tree}}_{3}^{({10})}({1})$ is just a tree of depth one, since
$y^{2}=3^{10}\bmod{3^{11}}$ iff $y=\widetilde{x}3^{5}$ with
$\gcd(\widetilde{x},3)=1$ and $1\leq\widetilde{x}\leq 3^{6}$, and there are
$\varphi(3^{6})=486$ such $\widetilde{x}$’s, so
${\mathrm{Tree}}_{3}^{({10})}({1})\cong T_{486}^{(1)}$ is just a regular tree
of width $486$ and depth $1$. Similarly, ${\mathrm{Tree}}_{3}^{({6})}({1})$ is
a tree of depth 1 and width $\varphi(3^{3})=2\cdot 3^{2}=18$.

The more complicated case is ${\mathrm{Tree}}_{3}^{({8})}({1})$. Note that
$8=2^{3}$, so we can consider the unfurled graph of depth three
$Z_{3}({1},{3})$, see Figure 2. According to Lemma 2.3.12, we take this graph
and expand it by the powers $3^{4},3^{2},3^{1}$, so that the in-neighborhood
of $x=3^{8}$ has $3^{4}$ leaves coming in, and $3^{4}$ trees of type
${\mathrm{Tree}}_{3}^{({4})}({1})$, which themselves have $3^{2}$ leaves
coming in, and $3^{2}$ trees coming in, and those are regular trees of the
form $T_{6}^{1}$. (And of course, for any $\widetilde{x}3^{8}$ with
$\widetilde{x}\equiv 1\bmod 3$ we get an isomorphic tree, so there are $9$ of
them.) See Figure 10 for a visualization of
${\mathrm{Tree}}_{3}^{({8})}({1})$, which is also complicated and fun. (We
would have liked to put a visualization of the full $\mathcal{N}({3^{11}})$
here but at $59,049$ vertices and $177,147$ edges, it made our computer sad.)

Figure 10: The subgraph of $\mathcal{G}({3^{11}})$ that goes to $x=3^{8}$,
giving an example of ${\mathrm{Tree}}_{3}^{({8})}({1})$. Its details are given
in the text, but note that there are nine copies of this bad boy attached to
zero, not to mention all of the other things going in (see Table 2).

##  4 Conclusions

We have presented some basic theory and give a few nice examples. The examples
were a lot of fun, and there’s no doubt that one can find a whole host of
other interesting examples. I leave it to the readers of this article to
explore and find more.

## References

  * [1] Troy Vasiga and Jeffrey Shallit.  On the iteration of certain quadratic maps over GF(p).  Discrete Mathematics, 277(1-3):219–240, 2004.
  * [2] Lee DeVille.  What does $x^{2}\bmod n$ look like??? YouTube video, May 17, 2022. https://www.youtube.com/watch?v=RmqFm9HN3nw
  * [3] David Dummit and Richard Foote.  Abstract Algebra, volume 1999.  Prentice Hall Englewood Cliffs, NJ, 1991.
  * [4] Carl Friedrich Gauss.  Disquisitiones Arithmeticae.  English edition. translated by Arthur A. Clarke, 1986.