Is the Collatz function piecewise linear?

408 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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." ;-)