\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}