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?

  • 4
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Jul 6 '17 at 8:08
  • $\begingroup$ @DietrichBurde thanks. Did you know of this apparent discrepancy already? $\endgroup$ – samerivertwice Jul 6 '17 at 8:14
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ thanks. I wasn't so confident in my own understanding of a permutation. If you add to your question confirmation of when a function is a permutation I can accept it. $\endgroup$ – samerivertwice Jul 6 '17 at 8:26
  • $\begingroup$ oeis.org/A006369 seems to be the sequence $\endgroup$ – celtschk Jul 6 '17 at 9:52
  • $\begingroup$ 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) $\endgroup$ – Gottfried Helms Jul 7 '17 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.