# When is a function a permutation of the integers?

When is a function a permutation of the integers?

In his 2011 paper on the Collatz conjecture here Lagarias writes;

> Collatz’s  original  function, which is a permutation of the integers...


But when is a function over the integers a permutation of the integers? My understanding would be that a permutation must be a bijection from a domain onto itself because only this will reposition every domain element uniquely in the range.

But if we consider the Collatz function exactly a sixth of the integers are mapped to by two distinct elements; namely every even number equivalent to $1\mod 3$, which is is mapped to by both $3x+1$ and $x/2$ e.g.the number 16.

This doesn't seem to be a permutation because $16$ and other numbers will appear multiple times in the range.

Where am I (or Lagarias) going wrong? If it's his mistake, what do you suppose he meant by this?

• Lagarias explains this on page 37; the original function of Collatz is a permutation of integers. It is not the function we are considering nowadays. – Dietrich Burde Jul 6 '17 at 8:08
• @DietrichBurde thanks. Did you know of this apparent discrepancy already? – samerivertwice Jul 6 '17 at 8:14
• No, I did not, but I suspected that the answer can be found in Lagarias paper. He is very reliable. And indeed, I found it quickly. – Dietrich Burde Jul 6 '17 at 8:17

Collatz original function was defined as follows: Consider the infinite permutation $$P ={1 2 3 4 5 6 \cdots \choose 1 3 2 5 7 4 \cdots}$$ taking $n\to f(n)$ where $f : \mathbb{N}^+ \mapsto \mathbb{N}^+$ is given by $$f(3n) = 2n, f(3n−1) = 4n−1, f(3n−2) =4n − 3.$$ This is different from the Collatz function defined in the $3n+1$-problem!
Reference: Jeffrey C. Lagarias: The $3x + 1$ Problem: An Annotated Bibliography (1963–1999); page 37.
Edit: A permutation of a set $X$ is an element of the group ${\rm Sym}(X)$ consisting of all bijective maps from $X$ to $X$. If $|X|=n$, then ${\rm Sym}(X)\cong S_n$, the symmetric group.
• I find it a bit more intuitive to write $f(3n) = 2n, f(3n−1) = 4n−1, f(3n+1) =4n+1$ (but that's subjective, of course) – Gottfried Helms Jul 7 '17 at 8:10