13
$\begingroup$

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.

Consider all permutations $\pi$ on the natural numbers such that for each $i$, $\pi(3i)=2i$ and $\lbrace \pi(3i+1),\pi(3i+2)\rbrace = \lbrace 4i+1,4i+3\rbrace$.

The question: Is there such a permutation for which all the cycles have finite length?

By computer it is easy to find choices that make the cycles containing the first several thousand integers finite.

$\endgroup$
  • $\begingroup$ Do you actually have any explicit example of such a permutation? Why do they exist? $\endgroup$ – Igor Rivin Aug 5 '15 at 14:03
  • $\begingroup$ @Igor: All such $\pi$ are injective and surjective if we choose $\pi(3i+1)\ne \pi(3i+2)$, thus they are all permutations, if this was your question. $\endgroup$ – domotorp Aug 10 '15 at 20:40
4
$\begingroup$

This is something between an extended comment and an answer, and might contain nothing that you haven't known already, but I am sure that the answer to your question is yes.

The reason is that there are only countable many cycles, so we can take care of them one by one to make them finite. Suppose up to some point all cycles containing numbers less than $n$ are finite and consider the cycle of $n$. It has two ends and at both ends we can make choices by picking the yet undecided values of $\pi(3i+1)$ and $\pi(3i+2)$ as we like. By making some choices, after a while the two ends will either meet, or both go to some very large values, which means that we can make many choices, as in that high range nothing was decided earlier. Since for your parameters $\frac 32 \cdot \frac 34<2$, the graph of the choices will behave like an expander, so the two ends can be made to meet.

$\endgroup$
  • 2
    $\begingroup$ That is basically how I tried by computer. It does seem to work empirically, but sometimes the cycles made were very long and I couldn't find a pattern of choices that always seemed to work. One heuristic is to favour multiples of 3 when faced with a choice (so that the next step decreases) but that sometimes appeared to fail. $\endgroup$ – Brendan McKay Aug 10 '15 at 22:46

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.