# Is the Collatz function piecewise linear?

I read somewhere that the Collatz function $\mathbb Z \rightarrow \mathbb Z$: $$\text{Collatz}(x) = \begin{cases} x/2 &&x \; \mathrm{even} \\ 3x+1 &&x \; \mathrm{odd}\end{cases}$$

is piecewise linear. But while it are two linear functions strung together, I can't cut it in finitely many intervals that are all linear.

So is the Collatz function piecewise linear or not?

• It depends on your definition. The "finitely many pieces" thing comes from piecewise xy functions on compact intervals, for functions defined on all of $\mathbb{R}$ it makes sense to call a function piecewise xy if you can cut $\mathbb{R}$ into pieces that have a certain minimal length such that the function is xy on (the closure of) each piece. But of course if you allow infinitely many pieces, and take $\mathbb{Z}$ as domain, then ... – Daniel Fischer Aug 26 '15 at 18:41

The answer, unfortunately, is: "It depends on the definitions in question." (For convenience, throughout this post, function domains and ranges are assumed to be subsets of the reals.)

For example, as Daniel points out in the comments above, saying that a function $f$ is piecewise linear is often intended to mean that the domain of $f$ can be partitioned into finitely-many intervals $I_1,...,I_n$ such that for each $I_k,$ the restriction of $f$ to $I_k$ is identical to the restriction of a function of the form $x\mapsto mx+b$ to the same interval. By that definition, the Collatz function fails to be piecewise linear, because for any partition of $\Bbb Z$ into finitely-many intervals, there is an interval in the partition such that three points in the interval yield non-colinear coordinates.

Another feasible definition is that a function $f$ is piecewise linear if there is a finite partition of the domain of $f$ into sets $A_1,...,A_n$ such that for each $A_k,$ the restriction of $f$ to $A_k$ is identical to the restriction of a function of the form $x\mapsto mx+b$ to the same set. By that definition, the Collatz function is piecewise linear immediately, by partitioning $\Bbb Z$ into the set of even numbers and the set of odd numbers.

Another possible definition is that a function $f$ is piecewise linear if there is a partition of the domain of $f$ into a family $\mathcal A$ of sets such that for each $A\in\mathcal A,$ the restriction of $f$ to $A$ is identical to the restriction of a function of the form $x\mapsto mx+b$ to the same set. By that definition, the Collatz function is piecewise linear, for the same reason. As Hagen points out in the comments below, this definition is unrevealing. Note in particular that we can always partition the domain of a function $f$ into sets of the form $\{x:f(x)=y\}$ for $y$ in the range of $f$, and $f$ is constant when restricted such sets, so every real-valued function would be piecewise linear by this definition.

Another possible definition is that a function $f$ is piecewise linear if there is a partition of the domain of $f$ into a family $\mathcal I$ of intervals such that for each $I\in\mathcal I,$ the restriction of $f$ to $I$ is identical to the restriction of a function of the form $x\mapsto mx+b$ to the same set. By that definition, the Collatz function is piecewise linear, by partitioning $\Bbb Z$ into the countably-many degenerate intervals $[n,n]=\{n\}$ for $n\in\Bbb Z.$ But just like the preceding definition, every real-valued function is piecewise linear under this definition.

I can think of several other possible definitions (only some of which are satisfied by the Collatz function), and I'm sure that there are definitions I haven't thought of, which the Collatz function may or may not satisfy. The upshot is: be aware of the definitions your source is using.

Don't even get me started on the definition of "linear." ;-)

• The second definition would lead to Dirichlet's function $1_{\mathbb Q}$ piecewise linear, which I don't think is desirable ... (and the third one seems to make every function $\mathbb R\to\mathbb R$ piecewise linear, by taking $\mathcal A=\{\{x\}\mid x\in \mathbb R\}$). – Henning Makholm Oct 21 '15 at 19:48
• True. Note that I didn't say that the definitions were desirable, just possible. ;-) Good observation about the third definition. – Cameron Buie Oct 21 '15 at 20:05