Maximal cardinality of $(n,2^{-k})$-separated set and minimal cardinality of $(n,2^{-k})$-spanning set

166 Views Asked by At

Let $A$ be some finite alphabet and consider the set $$ X=\{x=(x_i)_{i\in\mathbb{Z}}\in A^{\mathbb{Z}}: x_i\in A\forall i\in\mathbb{Z}\} $$ of bi-infinite sequences with entries in $A$. On $X$, I am considering the left-shift map defined by $$ (\sigma(x))_i=x_{i+1}. $$

Moreover, on $X$, define the metric $$ d(x,y)=2^{-k} $$ with $k$ maximal such that $x_{[-k,k]}=y_{[-k,k]}$. Here $$x_{[-k,k]}=(x_{-k},\ldots,x_{-1},x_0,\ldots,x_1,\ldots,x_k),$$ is the central block of length $2k+1$ around position $0$.

The convention is that $k=-1$ if $x_0\neq y_0$ and $k=\infty$ if $x=y$.

Define $$ d_n(x,y):=\max_{0\leq i\leq n-1}d(\sigma^i(x),\sigma^i(y)). $$

Let $\varepsilon >0$. A set $E\subset X$ is called $(n,\varepsilon)$-separated if for all $x,y\in E, x\neq y$, we have $$ d_n(x,y)>\varepsilon. $$ By $\text{sep}(n,\varepsilon)$ denote the maximal cardinality of an $(n,\varepsilon)$-separated set.

A set $E\subset X$ is called $(n,\varepsilon)$-spanning, if for all $x\in X$ there exists some $y\in E$ such that $$ d_n(x,y)\leq\varepsilon. $$ By $\text{spa}(n,\varepsilon)$, denote the minimal cardinality of a $(n,\varepsilon)$-set.

My question

For $(X,d)$ as defined above, I am searching for $\text{sep}(n,2^ {-k})$, i.e. the maximal cardinality of an $(n,2^{-k})$-separated set, and $\text{spa}(n,2^{-k})$ i.e. the minimal cardinality of an $(n,2^{-k})$-spanning set.

By $B_n(X)$, I denote the set of all blocks of length $n$ which can occur in elements $x\in X$.

My idea is that $$ \text{spa}(n,2^{-k})=\text{card}(B_{2k+n}) $$ and $$ \text{sep}(n,2^{-k})=\text{card}(B_{2k+n}), $$ i.e. both numbers coincide and equal the number of blocks of length $2k+n$ which can occur in elements of $X$.

Am I right? Would be nice to get some feedback.