if $f_{n}(x)=f(f_{n-1}(x))$then $f_{10}(x)=x,x\in [0,1]$

Question

Define the function $f:[0,1]\to[0,1]$ by the following. $$f(x)=\begin{cases} x+\dfrac{1}{2},&0\le x\le\dfrac{1}{2}\\ 2(1-x),&\dfrac{1}{2}<x\le 1. \end{cases}$$ Let $f_1(x)=f(x)$ and for each $n\in\mathbb{N}\cap[2,\infty)$, define $f_n(x)$ as $$f_{n}(x)=f(f_{n-1}(x)).$$ Finally, define the sets $A$ and $B$ by $$A=\{x\in[0,1]\,|\,f_{10}(x)=x\}, B=\left\{\dfrac{2}{15},\dfrac{2}{3},0,\dfrac{1}{2},1\right\}.$$

1. Determine the intersection of $A$ and $B$.
2. Determine the cardinality of $A$.

my idea: since $$0\le x\le\dfrac{1}{2},\Longrightarrow x+\dfrac{1}{2}\in [\dfrac{1}{2},1]$$ and $$\dfrac{1}{2}<x\le 1\Longrightarrow 2(1-x)\in [0,\dfrac{1}{2}]$$ so $$f_{2}(x)=f(f_{1}(x))=\begin{cases} 2(1-(x+\dfrac{1}{2}))=1-2x&0\le x\le \dfrac{1}{2}\\ 2(1-x)+\dfrac{1}{2}=\dfrac{5}{2}-2x&\dfrac{1}{2}<x\le 1 \end{cases}$$ follow. I think this problem will take some time to solve. Maybe there are other methods? Thank you

Answer 1

1. Overview

$$ \large\mathit{\mbox{``A picture is worth a 1000 words''}}^{\tiny\,\,\,\mbox{but is no rigorous proof}} $$

fp(x) = (x <= 0.5) ? (x + 0.5) : 2*(1 - x)
fp10(x) = fp(fp(fp(fp(fp(fp(fp(fp(fp(fp(x))))))))))
plot [0:1][0:1] fp10(x), x, 2.0/15, 2.0/3, 0, 1.0/2, 1

Fun aside, this gives a first orientation. Let us go through the candidates from $B$:

• $P_1 = 2/15$ (blue line) is hard to judge in this view, might be a sampling error or not a fixed point.
• $P_2 = 2/3$ (magenta line) nicely crosses $\mbox{id}(x) = x$, that one is in $A$
• $P_3 = 0$ (cyan line), can't see, have to think later (but should be easy)
• $P_4 = 1/2$ (brown line), looks like a hit
• $P_5 = 1$ (black line), can't see in this resolution

Now let the machine do again the hard work:

gnuplot> print p1, fp10(p1)
0.133333333333333 0.133333333333326
gnuplot> print p2, fp10(p2)
0.666666666666667 0.666666666666629
gnuplot> print p3, fp10(p3)
0 0.5
gnuplot> print p4, fp10(p4)
0.5 1.0
gnuplot> print p5, fp10(p5)
1 0.0

The development of $P_1$ is

gnuplot> print p1, f(p1), f2(p1), f3(p1), f4(p1), f5(p1)
0.133333333333333 0.633333333333333 0.733333333333333 0.533333333333333
0.933333333333334 0.133333333333333

2. Checking $A \cap B$

$$ \begin{align} f(P_1) & = f(2/15) = 2/15 + 1/2 = 19/30 > 1/2 \\ f(19/30) & = 2(1 - 19/30) = 11 / 15 > 1/2 \\ f(11/15) & = 2(1 - 11/15) = 8 / 15 > 1/2 \\ f(8/15) & = 2(1 - 8/15) = 14 / 15 > 1/2 \\ f(14/15) & = 2(1 - 14/15) = 2/15 = P_1 \end{align} $$

Thus $f_5(P_1) = P_1$ and therefore $f_{10}(P_1) = P_1$.

Then we have for $P_2$: $$ f(P_2) = f(2/3) = 2(1 - 2/3) = 2/3 = P_2 $$ and thus $f_{10}(P_2) = P_2$.

Now let us look at one iteration to see what is going on for $P_3, P_4, P_5$:

$$ f(P_3) = P_4, \quad f(P_4) = P_5, \quad f(P_5) = P_3 $$

Taking 10 iterations one gets $$ f_{10}(P_3) = P_4 \ne P_3, \quad f_{10}(P_4) = P_5 \ne P_4, \quad f_{10}(P_5) = P_3 \ne P_5. $$

It looks like $A \cap B = \{ P_1 = 2/15, P_2 = 2/3 \}$.

3. Counting $A$

Now about $|A|$ which I interpret as the number of fixed points of $f_{10}$ on $[0, 1]$.

For this we have to look at the fixed points of $f_1$, $f_2$, $f_5$ and $f_{10}$ to understand what is going on.

As one can see the graphical methods, counting crossings hits its limits for higher iterations. For $f_{10}$ one would need to look at small resolutions.

Estimation: With every evaluation of $f$ there is one comparison involved, so for $f_{10}$ we talk about up to $2^{10} = 1024$ cases here.

Let $s(k)$ be the number of straight line segments of $f_k$ then I counted

$$ s = (2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots) $$

on the graphs. This is obviously a Fibonacci series. So there should be $s(10) = 144$ straight line segments, which gives a first upper bound for the number of fixed points $|A|$. This is an observation, I can give no proof for $s(k)$ yet.

3.1 The Secant Method

Next I wrote a numeric fixed point solver and that spew out $|A| = 123$, using $1024$ subintervals. See program and output.

As $f_{10}$ is piecewise linear,

$$ x_0 = x, \\ x_k = a_k\, x_{k - 1} + b_k \quad (k > 0) \\ (a_k, b_k) \in \{ (1, 1/2), \, (-2, 2) \} $$

with rational coefficients $a_k$ and $b_k$

$$ f_{10}(x) = \alpha_{10} x + \beta_{10} \\ \alpha_{10} = \prod\limits_{k=1}^{10}a_k \\ \beta_1 = b_1 \\ \beta_{k} = a_k \, \beta_{k-1} + b_k \quad (k > 1) \\ f_{10}(x^*) = x^* \iff x^* = \frac{\beta_{10}}{1 - \alpha_{10}} \in \mathbb{Q} \quad(*) $$

the fixed points are rational numbers.

Thus I updated the numerical program to search and display the fractions. This yields:

$$ A = \left\{ \frac{2}{129}, \frac{1}{63}, \frac{5}{129}, \frac{2}{51}, \frac{8}{129}, \frac{4}{63}, \frac{14}{129}, \frac{1}{9}, \frac{17}{129}, \frac{2}{15}, \frac{20}{129}, \frac{8}{51}, \frac{86}{513}, \frac{43}{255}, \frac{23}{129}, \frac{46}{255}, \frac{26}{129}, \frac{13}{63}, \frac{29}{129}, \frac{58}{255}, \frac{32}{129}, \frac{16}{63}, \frac{38}{129}, \frac{19}{63}, \frac{1}{3}, \frac{22}{63}, \frac{50}{129}, \frac{25}{63}, \frac{53}{129}, \frac{106}{255}, \frac{56}{129}, \frac{4}{9}, \frac{62}{129}, \frac{31}{63}, \frac{65}{129}, \frac{26}{51}, \frac{133}{258}, \frac{65}{126}, \frac{68}{129}, \frac{8}{15}, \frac{139}{258}, \frac{55}{102}, \frac{278}{513}, \frac{139}{255}, \frac{71}{129}, \frac{142}{255}, \frac{145}{258}, \frac{71}{126}, \frac{74}{129}, \frac{37}{63}, \frac{77}{129}, \frac{154}{255}, \frac{157}{258}, \frac{11}{18}, \frac{80}{129}, \frac{32}{51}, \frac{163}{258}, \frac{19}{30}, \frac{326}{513}, \frac{163}{255}, \frac{83}{129}, \frac{166}{255}, \frac{169}{258}, \frac{67}{102}, \frac{338}{513}, \frac{169}{255}, \frac{341}{513}, \frac{2}{3}, \frac{685}{1026}, \frac{341}{510}, \frac{344}{513}, \frac{172}{255}, \frac{175}{258}, \frac{347}{510}, \frac{350}{513}, \frac{35}{51}, \frac{89}{129}, \frac{178}{255}, \frac{181}{258}, \frac{89}{126}, \frac{92}{129}, \frac{184}{255}, \frac{187}{258}, \frac{371}{510}, \frac{374}{513}, \frac{11}{15}, \frac{95}{129}, \frac{38}{51}, \frac{193}{258}, \frac{95}{126}, \frac{98}{129}, \frac{7}{9}, \frac{101}{129}, \frac{202}{255}, \frac{205}{258}, \frac{101}{126}, \frac{104}{129}, \frac{52}{63}, \frac{5}{6}, \frac{107}{126}, \frac{110}{129}, \frac{55}{63}, \frac{113}{129}, \frac{226}{255}, \frac{229}{258}, \frac{113}{126}, \frac{116}{129}, \frac{232}{255}, \frac{235}{258}, \frac{467}{510}, \frac{470}{513}, \frac{47}{51}, \frac{119}{129}, \frac{14}{15}, \frac{241}{258}, \frac{17}{18}, \frac{122}{129}, \frac{61}{63}, \frac{125}{129}, \frac{50}{51}, \frac{253}{258}, \frac{125}{126}, \frac{128}{129} \right\}, \, |A| = 123 $$

3.2 Looking for Cycles

Another update of the program yielded the partition of $A$ into

$$ A = A_1 \cup A_2 \cup A_5 \cup A_{10} $$

with

$$ A_{1} = \left\{ \frac{2}{3} \right\}, |A_{1}| = 1 \\ A_{2} = \left\{ \frac{1}{3}, \frac{5}{6} \right\}, |A_{2}| = 2 \\ A_{5} = \left\{ \frac{1}{9}, \frac{2}{15}, \frac{4}{9}, \frac{8}{15}, \frac{11}{18}, \frac{19}{30}, \frac{11}{15}, \frac{7}{9}, \frac{14}{15}, \frac{17}{18} \right\}, |A_{5}| = 10 = 2 \cdot 5\\ A_{10} = \left\{ \frac{2}{129}, \frac{1}{63}, \frac{5}{129}, \frac{2}{51}, \frac{8}{129}, \frac{4}{63}, \frac{14}{129}, \frac{17}{129}, \frac{20}{129}, \frac{8}{51}, \frac{86}{513}, \frac{43}{255}, \frac{23}{129}, \frac{46}{255}, \frac{26}{129}, \frac{13}{63}, \frac{29}{129}, \frac{58}{255}, \frac{32}{129}, \frac{16}{63}, \frac{38}{129}, \frac{19}{63}, \frac{22}{63}, \frac{50}{129}, \frac{25}{63}, \frac{53}{129}, \frac{106}{255}, \frac{56}{129}, \frac{62}{129}, \frac{31}{63}, \frac{65}{129}, \frac{26}{51}, \frac{133}{258}, \frac{65}{126}, \frac{68}{129}, \frac{139}{258}, \frac{55}{102}, \frac{278}{513}, \frac{139}{255}, \frac{71}{129}, \frac{142}{255}, \frac{145}{258}, \frac{71}{126}, \frac{74}{129}, \frac{37}{63}, \frac{77}{129}, \frac{154}{255}, \frac{157}{258}, \frac{80}{129}, \frac{32}{51}, \frac{163}{258}, \frac{326}{513}, \frac{163}{255}, \frac{83}{129}, \frac{166}{255}, \frac{169}{258}, \frac{67}{102}, \frac{338}{513}, \frac{169}{255}, \frac{341}{513}, \frac{685}{1026}, \frac{341}{510}, \frac{344}{513}, \frac{172}{255}, \frac{175}{258}, \frac{347}{510}, \frac{350}{513}, \frac{35}{51}, \frac{89}{129}, \frac{178}{255}, \frac{181}{258}, \frac{89}{126}, \frac{92}{129}, \frac{184}{255}, \frac{187}{258}, \frac{371}{510}, \frac{374}{513}, \frac{95}{129}, \frac{38}{51}, \frac{193}{258}, \frac{95}{126}, \frac{98}{129}, \frac{101}{129}, \frac{202}{255}, \frac{205}{258}, \frac{101}{126}, \frac{104}{129}, \frac{52}{63}, \frac{107}{126}, \frac{110}{129}, \frac{55}{63}, \frac{113}{129}, \frac{226}{255}, \frac{229}{258}, \frac{113}{126}, \frac{116}{129}, \frac{232}{255}, \frac{235}{258}, \frac{467}{510}, \frac{470}{513}, \frac{47}{51}, \frac{119}{129}, \frac{241}{258}, \frac{122}{129}, \frac{61}{63}, \frac{125}{129}, \frac{50}{51}, \frac{253}{258}, \frac{125}{126}, \frac{128}{129} \right\}, |A_{10}| = 110 = 11 \cdot 10 $$

where $A_k$ is the set of fixed points of order $k = \min\{ i \left|\,\, f_i(x^*) = x^* \right. \}$.

Answer 2

In a nice computation-based analysis, mvw observed a Fibonacci-like structure in the graphs of the functions $f_n$. This structure is easy to prove by thinking inductively about the composition of the function. Each graph consists of a sequence of "short" and "long" segments, where each short segment has $[1/2,1]$ for its range and each long segment has the entire interval $[0,1]$ for its range. Given the graph for $f$, each short segment becomes a long segment in the next iteration, while each long segment splits into a long segment plus a short segment (the split occurs at the midpoint). Symbolically, we have $s\to L$ and $L\to Ls$ at each iteration. This clearly leads to Fibonacci numbers: $s\to L\to Ls\to L^2s\to L^3s^2\to L^5s^3\to\ldots$.

Consequently, by $f_{10}$, the short segment for $f=f_1$ has split into $21$ short segments and $34$ long ones, while the long segment has split into $55$ long segments and $34$ short ones, for a total of $144$ segments, as mvw observed. The reason for keeping separate counts is for the purpose of determining the cardinality of the OP's set $A$, the solutions to $f_{10}(x)=x$: Each long segment intersects the straight line $y=x$ exactly once, but of the short segments, only the ones with domain in $[1/2,1]$ do so. Thus

$$|A|=34+55+34=123$$

which also agrees with what mvw found computationally.

As for the intersection of $A$ and $B=\{{2\over15},{2\over3},0,{1\over2},1\}$, I agree with the comment by N.S., that this is perhaps best found by straightforward computation of $f_{10}(x)$ for those five values.

One comment regarding mvw's graphs: The sawteeth there are much more ragged and irregular than they are in actuality -- in actuality, the max's and min's are all at $0$, $1/2$ and $1$. This flaw in the graphs is presumably because of default settings in the plotting algorithm (the fault is in default...). As mvw astutely said upfront, a picture is worth a thousand words, but is no rigorous proof.