Techniques for finding period points

Question

Consider the tent function $f_2$ given by:

$$f_2 = \begin{cases} 2x, & 0\leq x\leq \frac{1}{2} \\ 2-2x, & \frac{1}{2} < x \leq 1 \end{cases}$$ How do I find the periodic points of this map? (I need to prove that they are dense in $[0,1]$, but for now I'm just interested in finding the actual set.) More generally, are there any useful techniques for finding periodic points? Turning directly to the definition doesn't seem very useful, so where should I start looking when I try to tackle a problem like this one?

Edit: A periodic point is a point $x$ such that $f^n(x)=x$, where $f^n$ denotes the $n$th iterate of $f$; that is, the composition of $f$ with itself $n$ times.

Answer 1

Indeed the are dense.

The best way to see this is to draw the graph of $f^n$: $$ f^{n}(x)=\left\{ \begin{array}{ccc} 2^nx & \text{if} & x\in\big[0,\tfrac{1}{2^n}\big], \\ 1-2^nx\big(x-\tfrac{1}{2^n}\big) & \text{if} & x\in\big[\tfrac{1}{2^n},\tfrac{2}{2^n}\big], \\ 2^n\big(x-\tfrac{2}{2^n}\big) & \text{if} & x\in\big[\tfrac{2}{2^n},\tfrac{3}{2^n}\big], \\ & \vdots & \\ 1-2^nx\big(x-\tfrac{2^n-1}{2^n}\big) & \text{if} & x\in\big[\tfrac{2^n-1}{2^n},1\big], \end{array} \right. $$ So the line $y=x$ intersects the graph of $f^n$ at $2^n$ points, and hence $f^n$ has $2^n$ fixed points, one in each interval of the form $\big[\frac{k-1}{2^n},\frac{k}{2^n}\big]$.

See the graph of $f^3$ which has 8 fixed points.

Answer 2

1. Let us start with a related, maybe better known, case: the $\times2$ function $g$ is defined on $[0,1]$ by $$g(x) = \begin{cases} 2x, & 0\leq x\leq \frac{1}{2} \\ 2x-1, & \frac{1}{2} < x \leq 1 \end{cases}$$ and is such that, for every $n\geqslant1$ and $x$ in $[0,1]$, $$g^n(x)=2^nx\pmod{1},$$ hence the fixed points of $g^n$ solve $$2^nx=x+k,\qquad k\in\mathbb N,$$ from which one sees that every $$x=\frac{k}{2^n-1},\qquad0\leqslant k\leqslant2^n-1,$$ is periodic for $g$ with a period dividing $n$.

2. So far so good. But another approach to the iterates of $g$, based on dyadic expansions, is helpful. Namely, remember that every number $x$ in $[0,1]$ is $$x=\sum_{n\geqslant1}\frac{b_n(x)}{2^n},\qquad b_n(x)\in\{0,1\}.$$ One sees that $$g(x)=\sum_{n\geqslant1}\frac{b_{n+1}(x)}{2^n}\qquad(n\geqslant1).$$ Put succinctly, $g$ acts as a shift on the sequence $(b_n)$ in the sense that $$b_n(g(x))=b_{n+1}(x).$$ From this representation, a host of nice properties of the iterates of $g$ follows, amongst them its periodic points.

3. Rrrright... Now we turn to the setting of the question, where one iterates the function $f$ defined on $[0,1]$ by $$f(x) = \begin{cases} 2x, & 0\leq x\leq \frac{1}{2} \\ 2-2x, & \frac{1}{2} < x \leq 1 \end{cases}$$ After a bit of head-scratching, one may get the idea of using a slightly different expansion of every $x$ in $[0,1]$, namely, $$x=\frac12+\frac12\sum_{n\geqslant1}\frac{s_n(x)}{2^n},\qquad s_n(x)\in\{-1,1\}.$$ Then a computation similar to the one above shows that $f$ acts on $(s_n)$ as $$s_n(f(x))=-s_1(x)s_{n+1}(x)\qquad(n\geqslant0).$$ 4. And we are finally ready to deal with the question... Note that the fixed points of $f^n$ solve $$s_{k+n}(x)=-s_1(x)s_2(x)\cdots s_n(x)s_{k}(x)\qquad(k\geqslant1).$$ Put differently, for every initial family of signs $(\sigma_k)_{1\leqslant k\leqslant n}$, the number $x$ uniquely defined by the conditions that, for every $1\leqslant k\leqslant n$ and every $i\geqslant0$, $$s_{k+in}(x)=\tau^i\sigma_k,\qquad\tau=-\sigma_1\sigma_2\cdots\sigma_n,$$ is such that $f^n(x)=x$. In particular, $f^n$ has $2^n$ fixed points. Furthermore, the periodic points of $f$ are dense since every interval $$\{x\mid\forall1\leqslant k\leqslant n,s_k(x)=\sigma_k\}$$ has length $1/2^n$ and contains a periodic point.