13
$\begingroup$

For $r > 0$, define $f(n) = \lfloor {nr}\rfloor$ if $n$ is odd and $f(n) = \lfloor {n/r}\rfloor$ if $n$ is even. For which real numbers $r$ is the set $\{n,f(n), f(f(n)),\dots\}$ bounded for every nonnegative integer $n$?

So far, I have only computer-generated evidence. If $r = \sqrt 3$, the iterates reach $1$ for $n = 1,...,10^5$. If $r = \sqrt 5$, the iterates reach $0$ for $n = 1,...,10^5$. If $r = \sqrt 2$ and $n = 73$, the iterates appear to be unbounded. If $r = (1+\sqrt 5)/2$, it appears that the iterates are bounded if and only if $|n+1-2F| \le 1$ for some Fibonacci number $F$; the sequence of such $n$ begins with $0,1,2,3,4,5,6,8,9,10,14,15,16$.

A few more examples, in response to comments: if $r = 2^{1/3}$, the iterates for $n=9$ and $10 < n < 200001$ reach the cycle ${9,11,13,16,12}$. If $r = 2^{2/3}$, the iterates reach 1 for $n = 1,...,10^5$. For $r = e$ and $r = \pi$, the iterates reach $0$ for $n = 1,...,20000$. For $r = 1/9$, the iterates appear unbounded for many choices of $n$, whereas for $r = 2/9$, perhaps they are all bounded.

$\endgroup$
5
  • 2
    $\begingroup$ Do you know any irrational for which you can prove the iterates are bounded for all $n$? or for some $n$? or for which you can prove the iterates are unbounded? $\endgroup$ May 6, 2015 at 0:01
  • $\begingroup$ You might look at finding an expression for f(f(n)) and f(f(f(n))), just to see how things might bounce around. In particular, finding n and r so that floor nr preserves parity would be a useful tool for this problem. Gerhard "Might Also Make Pretty Pictures" Paseman, 2015.05.06 $\endgroup$ May 6, 2015 at 20:22
  • 3
    $\begingroup$ Are you interested in a measure-theoretic type result, e.g., the set of $r\in(0,\infty)$ with this property has measure $0$? Or are you interested specifically in what happens when $r$ is algebraic, as in your examples? Or even when $[\mathbb{Q}(r):\mathbb{Q}]=2$, again as in your exmaples? And what happens when $r\in\mathbb{Q}$? (Since you insist that $r$ be irrational, I assume you worked out that case.) $\endgroup$ May 6, 2015 at 21:05
  • $\begingroup$ If you allow integers isn't $r=2$ solution? $\endgroup$
    – joro
    May 8, 2015 at 15:26
  • $\begingroup$ Special case posted at mathoverflow.net/questions/206320/a-property-of-e $\endgroup$ May 12, 2015 at 0:04

3 Answers 3

4
$\begingroup$

Let me write the iteration as $x(k+1, r) = f(x(k,r)) =\lfloor r x(k,r) \rfloor$ if $x(k,r)$ is odd, $\lfloor x(k,r)/r \rfloor$ if $x(k,r)$ is even, where $x(0,r) = 1$ (for convenience). I claim there is an uncountable set of $r$ for which all $x(k,r)$ are odd, and in particular $x(k,r) \to \infty$ as $k \to \infty$. This will be constructed as the intersection of sets $E_m$, $m=0, 1, \ldots$, where each $E_m$ is the union of $2^m$ disjoint intervals $L_{m,j}$ and for each $(m,j)$ there is an odd integer $X(m,j)$ such that

  1. $L_{m,j} = \{r: r X(m,\lfloor j/2 \rfloor) \in [X(m+1,j), X(m+1,j)+1)\}$
  2. $x(m+1,r) = X(m+1,j)$ for $r \in L_{m,j}$.
  3. $L_{m+1,2j} \cup L_{m+1,2j+1} \subset L_{m,j}$

For $m=0$ we take $E_0 = L_{0,0} = [5,6)$, $X(0,0) = 1$ and $X(1,0) = 5$.

Suppose we have $L_{m,j}$, $X(m,j)$ as above. Then $L_{m,j} X(m+1,j)$ is an interval of length $X(m+1,j)/X(m,j) \ge 5$, so it contains at least two intervals of the form $[i,i+1)$ with $i$ odd. These $i$ will be $X(m+2,2j)$ and $X(m+2,2j+1)$. Then we have $L_{m+1,2j} = \{r: r X(m+1,j) \in [X(m+2,2j),X(m+2,2j)+1)\}$ and $L_{m+1,2j+2} = \{r: r X(m+1,j) \in [X(m+2,2j+1),X(m+2,2j+1)+1)\}$.

The intersection of the closures of the $E_m$ is a Cantor set, in particular of cardinality of the continuum, and with at most countably many exceptions (endpoints of the $L{m,j}$) its points all have all $x(k,r)$ odd.

$\endgroup$
1
  • $\begingroup$ I wonder if one could use some similar argument to prove that there is a non-empty set of $r$'s for which no sequence of iterates goes to infinity. $\endgroup$ May 12, 2015 at 14:29
4
$\begingroup$

It's easy to prove that for $r=3+2\sqrt{2}$ and for $n=1$ or $n=3$ the sequences of iterates diverge (as they satisfy some simple recursive relation).

$\endgroup$
1
  • $\begingroup$ Even simpler $r=2+\sqrt{3}$ and $n=1$. $\endgroup$ May 12, 2015 at 4:08
1
$\begingroup$

If you allow integers, $r=2$ is a solution.

If $n$ is odd, you reach the cycle $2n$,$2n/2$.

If $n$ is even you decrease it to $n/2$.

$\endgroup$
1
  • $\begingroup$ This is true of any even $r$ - the value decreases as long as the iterates are even, and as soon as one iterate is odd it enters the short cycle here (which might be of length 1, if the series goes to 0). $\endgroup$ May 9, 2015 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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