\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,amsfonts,amsthm,stmaryrd,mathrsfs,url}
\usepackage{graphicx}
\usepackage{epsf}
\usepackage[usenames]{color}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}[thm]{Example}
\newtheorem{ques}[thm]{Question}
\newtheorem*{collatzcon}{Collatz Conjecture}
\newtheoremstyle{TheoremNum}
{\topsep}{\topsep} %%% space between body and thm
{\itshape} %%% Thm body font
{} %%% Indent amount (empty = no indent)
{\bfseries} %%% Thm head font
{.} %%% Punctuation after thm head
{ } %%% Space after thm head
{\thmname{#1}\thmnote{ \bfseries #3}}%%% Thm head spec
\theoremstyle{TheoremNum}
\newtheorem{thmn}{Theorem}
\newtheorem{propn}{Proposition}
\newtheorem{lemn}{Lemma}
\newtheorem{corn}{Corollary}
\theoremstyle{definition}
\newtheorem*{dfn}{Definition}
\theoremstyle{remark}
\newtheorem*{rmk}{Remark}
\newtheorem*{sol}{Solution}
\newtheorem*{dis}{DISPROOF}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\lto}{\mathop{\longrightarrow\,}\limits}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf The Collatz Problem and Analogues
}
\vskip 1cm
\large
Bart~Snapp and Matt~Tracy\\
Department of Mathematics and Statistics \\
Coastal Carolina University \\
Conway, SC 29528-6054 \\
USA \\
\href{mailto:snapp@coastal.edu}{\tt snapp@coastal.edu} \\
\href{mailto:mjtracy@coastal.edu}{\tt mjtracy@coastal.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
In this paper, we study a polynomial analogue of the Collatz
problem. Additionally, we show an additive property of the Collatz
graph.
\end{abstract}
\section{Introduction}
In the Collatz problem, one starts with any positive integer and repeatedly applies the following function:
\[
C(n) = \begin{cases}
3n+1, & \text{if $n$ is odd;} \\
n/2, & \text{if $n$ is even.}
\end{cases}
\]
Will the iterated application of $C$ always produce the value $1$? As an example, consider how $C$ acts on $3$:
\[
3 \lto^C 10 \lto^C 5 \lto^C 16 \lto^C 8 \lto^C 4 \lto^C 2 \lto^C 1
\]
This seemingly innocent problem is also known as \textit{the $3x+1$
problem}, \textit{the Hailstone problem}, and \textit{the Syracuse
problem}, along with several other names. Despite its simplistic
nature, it has remained open since it was suggested by L.\ Collatz
while he was a student in the 1930's. To some, this problem is a
proverbial \textit{siren}, being seductive yet difficult at the same
time. For an in depth discussion of the problem see Lagarias \cite{jL87}.
A condensed version of the traditional Collatz function
$C(n)$ can be given:
\[
T(n) = \begin{cases}
(3n+1)/2, & \text{if $n$ is odd;} \\
n/2, & \text{if $n$ is even.}
\end{cases}
\]
We will use the following notation: Let $T^0(n) = n$ and inductively
define $T^{i}(n) = T(T^{i-1}(n))$. We can now state the
\textit{Collatz Conjecture}:
\begin{collatzcon}
Given any natural number $n$, there exists a natural number $i$ such
that $T^i(n) = 1$.
\end{collatzcon}
Since the Collatz problem is notoriously difficult, we do not seek to
study it directly. Rather, in Section~\ref{S:analogue} of this paper, we
study a map analogous to $T(n)$, which will act not on the integers,
but on a polynomial ring with coefficients in the ring of integers
modulo an integer $n$. In this ring, which we'll denote by $\Z_n[x]$,
we define a map $T_P(f)$ which acts on polynomials. The major results
of this section are:
\begin{thmn}[\ref{T:Z2}]
Given any polynomial $f\in\Z_2[x]$, there exists a natural number $i$
such that $T^i_P(f) = 1$. Hence the analogous statement of the Collatz
Conjecture is true in $\Z_2[x]$.
\end{thmn}
\begin{thmn}[\ref{T:Zn2}]
If $n\ne 2$, then there exists a natural number $i$ and a polynomial
$f\in\Z_n[x]$ of positive degree such that $T^i_P(f) = f$. Hence the
analogous statement of the Collatz Conjecture is false in $\Z_n[x]$
when $n\ne 2$.
\end{thmn}
While we find the results above to be interesting in their own right,
the study of the analogue to the Collatz problem in $\Z_2[x]$ lead us to
a new insight on the problem. In Section~\ref{S:graph} of this paper,
we show a fascinating arithmetic property of a graph which contains
the Collatz graph. Essentially, we have found a meaningful way to
combine the graph of the iterates of $T(n)$ on the positive integers
with the graph of the iterates of $T(n)$ on the negative integers. It
was through our study of the analogous problem in $\Z_2[x]$, where
addition looks identical to subtraction, that we were able to see this
connection.
During the course of this research, we utilized PARI/GP for aid in
intuition and insight, see \cite{PARI}. The code for the package we
wrote for this research can be downloaded from:
\[
\texttt{http://ww2.coastal.edu/snapp/}
\]
Finally we would like to mention that our results in
Section~\ref{S:analogue} were concurrent with a publication of Hicks,
Mullen, Yucas, and Zavislak, see \cite{HMYZ08}. We encourage the
reader to look into this paper.
\section{An analogous question for polynomials}
\label{S:analogue}
We will first discuss the case of our analogous map in $\Z_2[x]$, then
in $\Z_p[x]$ where $p$ is an odd prime, and finally in $\Z_n[x]$ where
$n$ is any composite.
\subsection{An affirmative result}
Given a polynomial $f\in \Z_2[x]$, define the following map, which we
are viewing as an analogue to $T(n)$:
\[
T_P(f) =\begin{cases}
((x+1)\cdot f+1)/x, & \text{if $f$ is not divisible by $x$;} \\
f/x, & \text{if $f$ is divisible by $x$.}
\end{cases}
\]
We are mimicking the relationship between even numbers and odd numbers
in the integers. In the integers, $1$ added to an odd number will
result in an even number. In $\Z_2[x]$, an element is either divisible
by $x$ or it is not. To some extent, we are viewing $x$ as $2$. Hence
when $f$ is not divisible by $x$, we multiply by $x+1$. The product
$(x+1)\cdot f$ will also not be divisible by $x$. Hence $(x+1)\cdot
f+1$ will be divisible by $x$.
Of particular interest is that $\deg(T_P(f)) \le \deg(f)$. In fact, it
is easy to see that $\deg(T_P(f)) = \deg(f)$ when $x$ does not divide
$f$. This simple fact is critical in the proof of Theorem~\ref{T:Z2}
below. As before, set $T^0_P(f) = f$ and inductively define
$T^{i}_P(f) = T_P(T^{i-1}_P(f))$.
\begin{thm}\label{T:Z2}
Given any polynomial $f\in\Z_2[x]$, there exists a natural number $i$
such that $T^i_P(f) = 1$. Hence the analogous statement of the Collatz
Conjecture is true in $\Z_2[x]$.
\end{thm}
\begin{proof}
Seeking a contradiction, suppose that for some nonconstant polynomial
$f\in\Z_2[x]$ there does not exist a natural number $i$ such that
$T^i_P(f) = 1$. Since the function $T_P$ does not raise the degree of
the polynomial, and since there are only a finite number of
polynomials of any fixed degree in $\Z_2[x]$, it must be the case that
for some $i_0$, $T_P^{i_0}(f) = f$. In this case, for each $i$,
$T_P^i(f)$ must have a constant term equal to $1$. Write
\[
T_P^0(f) = 1 + \sum_{i = 1}^n a_i x^i
\]
So we have that
\[
T_P^1(f) = 1 + \sum_{i = 1}^n a_i x^{i} + \sum_{i = 1}^n a_{i} x^{i-1}
\]
In particular, since the constant term of this polynomial must be $1$,
we see that $a_1 = 0$. Repeating this process, starting our indexing at
$2$, write
\[
T_P^2(f) = 1 + \sum_{i = 2}^n a_i x^{i} + \sum_{i = 2}^n a_{i} x^{i-2}
\]
Again, if the constant term of this polynomial must be $1$, then we
must have that $a_2 = 0$. Proceeding inductively, we see that there
can be no polynomial of positive degree such that $T_P^i(f) =
f$. Indeed, we see that $f = 1$, a contradiction.
\end{proof}
\subsection{A negative result}
One may wonder if the analogous statement of the Collatz Conjecture is
true in $\Z_n[x]$ when $n>2$. In this case we need to generalize the
definition of $T_P(f)$ as follows:
\[
T_P(f) =\begin{cases}
((x+1)\cdot f-f(0))/x, & \text{if $f$ is not divisible by $x$;} \\
f/x, & \text{if $f$ is divisible by $x$.}
\end{cases}
\]
Note, with this new definition of $T_P$, we are not necessarily
restricting ourselves to working with polynomial rings over finite
fields. Moreover, we should make precise exactly what we mean by an
analogue to the Collatz conjecture in this case:
\begin{quote}
There do not exist nonconstant polynomials $f\in \Z_n[x]$ such that
$T_P^i(f) = f$.
\end{quote}
While Theorem~\ref{T:Z2}, shows that this statement is true in
$\Z_2[x]$, we will now show that this statement is in fact false in
$\Z_n[x]$ for all $n>2$. We will prove this in steps, starting with
$\Z_p[x]$ where $p$ is an odd prime and then move on to the case of
$\Z_n[x]$ when $n$ is composite. We will start with a technical lemma:
\begin{lem}\label{L:precycle} Given two integers $m\ge n$ we have the following:
\[
T_P^{n}(x^m+1) = \binom{n}{n} x^m + \binom{n}{n-1} x^{m-1} + \cdots + \binom{n}{0} x^{m-n} + 1
\]
\end{lem}
\begin{proof} Proceeding by induction on the iterations of $T_P$. To start, we see that
\begin{align*}
T_P(x^m+1) &= \frac{(x+1)(x^m+1)-1}{x} \\
&= \frac{x^{m+1} + x^m + x}{x} \\
&= x^m + x^{m-1} + 1.
\end{align*}
Now suppose our theorem is true up to $n-1$, that is, assume that:
\[
T_P^{n-1}(x^m+1) = \binom{n-1}{n-1} x^m + \binom{n-1}{n-2} x^{m-1} + \cdots + \binom{n-1}{0} x^{m-(n-1)} + 1
\]
We now can express $T_P^n(x^m+1)$ as:
\begin{align*}
&= \frac{(x+1)\left(\binom{n-1}{n-1} x^m + \cdots + \binom{n-1}{0} x^{m-(n-1)} + 1\right) - 1}{x}\\
&= \frac{\binom{n-1}{n-1} x^{m+1} + \left(\binom{n-1}{n-1} + \binom{n-1}{n-2}\right) x^m + \cdots + \left(\binom{n-1}{1}+ \binom{n-1}{0} \right)x^{m-n} + \binom{n}{0} x^{m-(n-1)} + x}{x}\\
&= \frac{\binom{n}{n} x^{m+1} + \binom{n}{n-1} x^m + \cdots + \binom{n}{1}x^{m-n} + \binom{n}{0} x^{m-(n-1)}+x}{x} \\
&= \binom{n}{n} x^m + \binom{n}{n-1} x^{m-1} + \cdots + \binom{n}{1}x^{m-(n-1)} + \binom{n}{0} x^{m-n} +1
\end{align*}
With the above line holding as long as $m\ge n$.
\end{proof}
\begin{prop}\label{P:prime}
If $p$ is an odd prime, then $T_P^p(x^{p-1} + 1) = x^{p-1} + 1$.
Hence the analogous statement of the Collatz Conjecture is false in
$\Z_p[x]$.
\end{prop}
\begin{proof} From Lemma~\ref{L:precycle}, we see that:
\[
T_P^{p-1}(x^{p-1} + 1) = x^{p-1} + \binom{p-1}{p-2} x^{p-2} + \cdots + \binom{p-1}{1} x + 2
\]
Hence:
\begin{align*}
T_P^{p}(x^{p-1}+1) &= \frac{x^p + \left(\binom{p-1}{p-2} +1 \right) x^{p-1} + \cdots + \left(\binom{p-1}{1}+2\right) x}{x} \\
&= x^{p-1} + \binom{p}{p-1} x^{p-1} + \cdots + \binom{p}{1} x + \binom{p}{1} + 1
\end{align*}
Examining this expression modulo $p$, we see that $T_P^{p}(x^{p-1}+1)
= x^{p-1}+1$.
\end{proof}
When working in $\Z_n[x]$ when $n$ is composite, the proof given above
may not work as $\binom{n}{m}$ might not be congruent to zero modulo
$n$. Nevertheless, we have the following proposition:
\begin{prop} \label{P:comp}
If $n$ is a composite integer with $d$ dividing $n$, then
$T_P^{n/d}(dx + 1) = dx + 1$. Hence the analogous statement of
the Collatz Conjecture is false in $\Z_n[x]$.
If $n$ is a composite number, then there exists a natural number $i$
and a polynomial $f\in\Z_n[x]$ of positive degree such that $T^i_P(f)
= f$. Hence the analogous statement of the Collatz Conjecture is false
in $\Z_n[x]$ when $n$ is composite.
\end{prop}
\begin{proof}
Supposing that $n$ is composite and that $d$ divides $n$. It is easy
to see that $T_P(dx+1) = dx + (d+1)$ and that:
\[
T_P^i(dx+1) = dx+ (di+1)
\]
Hence we see $T_P^{n/d}(dx+1) = dx+ (n+1)$, which is congruent to $dx+1$
modulo $n$. \end{proof}
Putting the statements of Proposition~\ref{P:prime} and
Proposition~\ref{P:comp} together, we obtain:
\begin{thm}\label{T:Zn2}
If $n\ne 2$, then there exists a natural number $i$ and a polynomial
$f\in\Z_n[x]$ of positive degree such that $T^i_P(f) = f$. Hence the
analogous statement of the Collatz Conjecture is false in $\Z_n[x]$
when $n\ne 2$.
\end{thm}
One may wonder if there exists a polynomial $f$ in $\Z_p[x]$ when $p$
is a prime of such that $T_p^i(f) = f$ and $\deg(f) < p-1$. In fact
there are many such examples. However, we will leave the
classification of such polynomials for future researchers.
\section{Connections to the Collatz graph}
\label{S:graph}
While we can prove a result analogous to the Collatz Conjecture in
$\Z_2[x]$, it is difficult to connect this back to the whole-number
case. Nevertheless, we are able to gain insight on the Collatz problem
through our study of $\Z_2[x]$. In particular, in $\Z_2[x]$ there is
no distinction between an element and its additive inverse. With this
fact in mind, we make the following definitions:
\begin{dfn} Call the standard Collatz graph of the iterates of
$T(n)$, the \textbf{positive Collatz graph}. This graph generated as
follows: Each integer $n$ is associated to a vertex. Vertices $n$
and $m$ are connected by an edge if and only if $T(n)= m$. We will
depict this graph as a directed graph with an arrow from $n$ to $m$
if $T(n) = m$, see Figure~\ref{F:cg}.
\begin{figure}[htp]
\centering
\includegraphics{graph0.eps}
\caption{\label{F:cg} A portion of the positive Collatz graph.}
\end{figure}
On the other hand, call the Collatz graph of the iterates of $T(n)$,
when $n$ is assumed to be a negative integer, the \textbf{negative
Collatz graph}.
\end{dfn}
We will make a new graph, combining the positive Collatz graph and the
negative Collatz graph which we will call the \textit{combined Collatz
graph}. If the Collatz Conjecture is true, then this new graph will
have the positive Collatz graph as a subgraph. Moreover, the combined
Collatz graph has an additive property between the vertices which we
will make clear below. Start with a technical lemma:
\begin{lem}\label{L:add}
Consider any integer $n$ which is not divisible by $3$. Then there exist
unique $x,y\in\N$ such that $2n = x+ y$ and exactly one of the
following is true:
\begin{enumerate}
\item $T(x) = n$ and $T(-y) = - 2n$.
\item $T(-x) = -n$ and $T(y) = 2n$.
\end{enumerate}
\end{lem}
\begin{proof}
Since $n$ is an integer which is not divisible by $3$,
\[
n = 3k + 1 \qquad \text{or} \qquad n = 3k + 2
\]
for some $k \in \Z$. A direct calculation will show that in either
case exactly one of the following pairs
\[
(x,y) = \left(\frac{2n-1}{3},\frac{4n+1}{3}\right) \qquad\text{or}
\qquad(x,y)=\left(\frac{2n+1}{3}, \frac{4n-1}{3}\right)
\]
is a pair of odd integers, with the other pair consisting of rational
numbers which are not integers.
We will verify our statement in the case where the first pair above
consists of odd integers. Set $x = (2n-1)/3$ and set $y =
(4n+1)/3$. It is easy to see that $x+y = 2n$. Moreover since $x$ and
$y$ are odd, a direct calculation shows that $T(x) = n$ and $T(-y) =
-2n$. The fact that these values of $x$ and $y$ are unique is clear
from the definition of $T$. The verification of the second case is
similar.
\end{proof}
\begin{rmk}
If $n$ is divisible by $3$, then there is no integer $x$ such that
$(3x+1)/2 = n$.
\end{rmk}
We are now able to generate a graph as follows: Starting with any
integer $n$ which is not divisible by $3$, work as in
Lemma~\ref{L:add} and set
\[
x = \begin{cases}
(2n - 1)/3 & \text{if $n \equiv 2 \pmod{3}$;}\\
(2n + 1)/3 & \text{if $n \equiv 1 \pmod{3}$.}
\end{cases}
\]
Now we may obtain $y$ via subtraction:
\[
y = 2n - x
\]
Since there are two cases for the $x$ and $y$ values we find, there
are two cases of subgraphs:
\[
\underbrace{\includegraphics{graphg1.eps}}_{\substack{n \equiv 2 \pmod{3} \\ x = (2n-1)/3 \\ y = (4n+1)/3}} \qquad\qquad
\underbrace{\includegraphics{graphg2.eps}}_{\substack{n \equiv 1 \pmod{3} \\x = (2n+1)/3\\ y = (4n-1)/3}}
\]
The dotted edges above should not be considered part of the graph,
they are only depicted to aid the reader in seeing how we produce the
next vertex through subtraction.
\begin{cor}\label{C:sub}
With $x$ and $y$ as defined above, if $n \equiv 2 \pmod{3}$, then we
have subgraphs
\[
\includegraphics{graphpg1.eps} \qquad\qquad
\includegraphics{graphng1.eps}
\]
of the positive Collatz graph, and negative Collatz graph
respectively.
If $n \equiv 1 \pmod{3}$, then we have subgraphs
\[
\includegraphics{graphpg2.eps} \qquad\qquad
\includegraphics{graphng2.eps}
\]
of the positive Collatz graph, and negative Collatz graph
respectively.
\end{cor}
\begin{proof} Follows directly from the statement of Lemma~\ref{L:add}.
\end{proof}
\subsection{Construction of the combined Collatz graph}
The \textbf{combined Collatz graph} is constructed as follows:
Starting with $n=1$, repeatedly apply Lemma~\ref{L:add} to the powers
of $2$ to generate the subgraph given in Figure~\ref{F:ccg1}.
\begin{figure}[htp]
\centering
\includegraphics{graph11.eps}
\caption{\label{F:ccg1} A start at the combined Collatz graph.}
\end{figure}
Here the dotted lines show how to produce the next vertex via
subtraction. By Corollary~\ref{C:sub}, the solid vertices above
correspond to vertices of the positive Collatz graph and hollow
vertices above correspond to the vertices of the negative Collatz
graph.
Now consider the vertices which are not multiples of $2$ which
correspond to vertices of the positive Collatz graph. These are either
congruent to $0$, $1$, or $2$ modulo $3$. Omitting the vertex denoted
by $1$, apply Lemma~\ref{L:add}, to generate the next branches of the
graph, see see Figure~\ref{F:ccg2}.
\begin{figure}[htp]
\centering
\includegraphics{graph12.eps}
\caption{\label{F:ccg2} More of the combined Collatz graph.}
\end{figure}
By repeating this process inductively, we obtain the combined Collatz
graph, see Figure~\ref{F:ccg}.
\begin{figure}[htp]
\centering
\includegraphics{graph1.eps}
\caption{\label{F:ccg} A portion of the combined Collatz graph.}
\end{figure}
\begin{cor}
The positive Collatz graph is a subgraph of the combined Collatz graph
if and only if the Collatz Conjecture holds.
\end{cor}
\begin{proof}
If the positive Collatz graph is a subgraph of the combined Collatz
graph, then each positive integer must eventually go to $1$, as we
generated this graph starting at $1$.
If the Collatz Conjecture is true, then there is a path to $1$ and
this construction will find it.
\end{proof}
The surprising feature of the combined Collatz graph is that using
very simple arithmetic allows for quick and easy generation of the
graph. Through this expedient process, we obtain a graph which has
the positive Collatz graph as an identifiable subgraph, assuming that
the Collatz Conjecture is true. Moreover, note that the construction
of the combined Collatz graph is in some sense, \textit{fundamentally
different} from the construction of either the positive Collatz graph
or the negative Collatz graph. The insight of looking at both the
positive Collatz graph and the negative Collatz graph was gained only
through the study of the analogous problem in $\Z_2[x]$.
\section{Acknowledgments}
We would like to thank Doug Shaw and David Duncan for reading over a
preliminary draft of this manuscript and making several helpful
comments. We would also like to thank the anonymous referee for his or
her comments as well.
%\bibliographystyle{plain}
%\bibliography{csources.bib}
%\end{document}
\begin{thebibliography}{1}
\bibitem{HMYZ08}
K. Hicks, G.~L. Mullen, J.~L. Yucas, and R. Zavislak,
\newblock A polynomial analogue of the $3n+1$ problem.
\newblock {\em Amer. Math. Monthly} \textbf{115} (2008), 615--622.
\bibitem{jL87}
J.~C. Lagarias,
\newblock The {$3x+1$} problem and its generalizations.
\newblock {\em Amer. Math. Monthly} \textbf{92} (1985), 3--23.
\bibitem{PARI}
{The PARI~Group}, Bordeaux.
\newblock {\em {PARI/GP, version \texttt{2.3.2}}}, 2005.
\newblock available from \url{http://pari.math.u-bordeaux.fr/}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11T55; Secondary 11B25.
\noindent \emph{Keywords: } Collatz conjecture, polynomial analogue
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A061641}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received May 22 2008;
revised version received October 31 2008.
Published in {\it Journal of Integer Sequences}, November 16 2008.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}