Show that $S= \{ \left(\frac{i}{k},\frac{j}{nk} \right) : 0 \leq i < k, 0 \leq j < nk \} $ is an $(n,\epsilon)$-spanning set

209 Views Asked by At

Let $\mathbb{T}^2=\mathbb{R}^2 / \mathbb{Z}^2$. Let $T: \mathbb{T}^2 \rightarrow \mathbb{T}^2$ be the transformation. Let $\alpha \in \mathbb{R}$.

$$T(x,y)=\left(x+\alpha \mod 1, x+y \mod 1 \right) $$.

One can show that $\displaystyle T^n(x,y)=\left(x+n\alpha \mod 1, y+nx+\frac{n(n-1)}{2}\alpha \mod 1 \right)$.

Show that if k is an integer such $\displaystyle\frac{1}{k}<\frac{\epsilon}{2}$, the set S given by

$$S= \left\{ \left(\frac{i}{k},\frac{j}{nk} \right) : 0 \leq i < k, 0 \leq j < nk \right\} $$

is an $(n,\epsilon)$-spanning set.

DEFINITION: Let $\epsilon >0, n \in \mathbb{N}$. A set $S \subset X$ is $(n,\epsilon)$-spanning set if for all $x \in X$, $\exists \ y \in S$ such that $d_n(x,y)< \epsilon$.

DEFINTION(ish): $\displaystyle d_n(x,y)=\max_{0 \leq k <n} d(f^k(x),f^k(y))$ for a given f (in this case T).

I draw a grid on the unit square $[0,1]^2$ given by $S$, but cannot see how to calculate $d_n(x,y)$.

1

There are 1 best solutions below

8
On BEST ANSWER

You don't need to compute exactly $d_n$, but to bound it. I assume that the distance used on $\mathbb{T}^2$ is the following:

$$d((x,y),(x',y')) = \hat{d} (x,x')+ \hat{d} (y,y'),$$

where $\hat{d}$ is the distance on $\mathbb{T}^1$.

Let $n > 0$. Then, for all $(x,y)$ and $(x',y')$ in $\mathbb{T}^2$, for all $k < n$:

$$\hat{d} \left( x+k\alpha, x'+k \alpha \right) = \hat{d} \left(x, x'\right),$$

and:

$$\hat{d} \left( y+kx+\frac{k(k-1)}{2} \alpha, y'+kx'+\frac{k(k-1)}{2} \alpha \right) = \hat{d} \left( y+kx, y'+kx'\right) \leq \hat{d} \left( y, y'\right) + k \hat{d} (x,x').$$

Hence:

$$d \left( T^k (x,y), T^k (x',y') \right) \leq (k+1) \hat{d} (x,x') + \hat{d} \left( y, y'\right).$$

Taking the maximum for all $k < n$, we finally get:

$$d_n \left( (x,y), (x',y') \right) \leq n \hat{d} (x,x') + \hat{d} \left( y, y'\right).$$

Now, let $\varepsilon > 0$, let $k > \varepsilon^{-1}$, and:

$$S' := \left\{ \left( \frac{i}{nk}, \frac{j}{k}\right): \ 0 \leq i < nk, \ 0 \leq j < k \right\}.$$

Pick $(x,y) \in \mathbb{T}^2$. Then there exists $i$ such that $\hat{d} \left(x, i/(nk)\right) < \varepsilon/(2n)$, and there exists $j$ such that $\hat{d} \left(y, j/k\right) < \varepsilon/2$. From there,

$$d_n \left( \left(x,y \right), \left(\frac{i}{nk},\frac{j}{k} \right) \right) \leq n\hat{d} \left(x, \frac{i}{nk}\right)+ \hat{d} \left( y, \frac{j}{k} \right) < n\frac{\varepsilon}{2n} + \frac{\varepsilon}{2} = \varepsilon.$$

Hence, $S'$ is a $(n, \varepsilon)$-spanning set. It is also a $(n, \varepsilon)$-spanning set for the Euclidean distance, which is smaller than the distance I used.

Two remarks:

  • I used the usual (translation invariant) distance on the circle $\mathbb{T}^1$. That allows me to gain a factor of $2$ in the definition of $S'$, since I only need to take $k > \varepsilon^{-1}$. If you work with the Euclidean distance on $[0,1)$, then you need to take $k \geq 2 \varepsilon^{-1}$ (otherwise, points close to $1$ are too far from the spanning set). Since I don't know the definition you took, I had to choose.

  • The question as you stated is false, and you have to invert the coordinates in the definition of $S$.