Proving that $S=\bigcup_{j=0}^{2^k-1} S_{n-1+k}$ is a spanning set for the $2$-D Baker map

Question

A set $S \subset X$ is a $(n,\epsilon)$-spanning set if $\forall x \in X$, $\exists y \in S $ such that $d_n(x,y)<\epsilon$. This is where we define $d_n(x,y)$ by $d_n(x,y)=\max_{0\leq k < n}d(f^k(x),f^k(y)$ for some topological dynamical system $f:X \rightarrow X$.

Let $X=[0,1]^2$ and let us take $f=F$ to be the two dimensional baker map defined by:

$F(x,y = \left\{ \begin{array}{ll} (2x,\frac{y}{2}) & \mbox{if } 0 \leq x < \frac{1}{2} \\ (2x-1,\frac{y+1}{2}) & \mbox{if } \frac{1}{2} \leq x < 1 \end{array} \right.$

Let $\epsilon = 1/2^k$. Let $S_{n}(y)=\{(\frac{i}{2^{n}},y) : 0 \leq i \leq 2^n-1 \}$. Then consider the set of points

$S = \bigcup_{j=0}^{2^k-1} S_{n-1+k}(\frac{j}{2^k})$

and show that it is an $(n,\epsilon)$-spanning set for the baker map $F$.

If we let $x \in X$ I then get that $x$ lies in some square $\displaystyle [\frac{i}{2^{n-1+k}},\frac{i+1}{2^{n-1+k}}] \times [\frac{j}{2^k},\frac{j+1}{2^k}]$ for some $i,j \in S$. However I cannot see a way such that $d_n(F(x),F(y) < \epsilon=\frac{1}{2^k}$ for some $y \in S$.

Applying $F$ to the $x$ coordinate I get that $F^{n-1}(x,y)=(2^{n-1}x,\frac{1}{2^{n-1}}y)$, which seems to get back to where we started and doesnt provide much help to solving the question.

I am now stuck on where to go now.

Answer 1

First try to understand what $F$ does to each one of those squares: $\left[\frac{i}{2^{n}},\frac{i+1}{2^n}\right]\times\left[\frac{j}{2^n},\frac{j+1}{2^n}\right]$ (visualize $F$ on the entire square as in the notes to understand its action - squeezing in one direction but stretching in the other).

Now what happens if you iterate $F$ (up to $n$ times)? How does this turn out for the $n$-step Bowen metric then? Which points are already "covered" by a single square in the first $n$ steps?

Finally think about how many (which) of those squares (better rectangles) you would need to $(n,\varepsilon)$-span the entire phase space $[0,1]^2$. This is where you want to change the initial shape from being a square $\left[\frac{i}{2^{n}},\frac{i+1}{2^n}\right]\times\left[\frac{j}{2^n},\frac{j+1}{2^n}\right]$ to a rectangle $\left[\frac{i}{2^{n-1+k}},\frac{i+1}{2^{n-1+k}}\right]\times\left[\frac{j}{2^k},\frac{j+1}{2^k}\right]$. Picking a single point from each one of those rectangles is gives you the $(n,\varepsilon$-spanning set $S$.