14
$\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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you actually have any explicit example of such a permutation? Why do they exist? $\endgroup$
    – Igor Rivin
    Commented Aug 5, 2015 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
    Commented Aug 10, 2015 at 20:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 4
    $\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
    Commented Aug 10, 2015 at 22:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .