2

For an element $x \in \{0,1\}^{\mathbb{Z}}$, define $S(x) = \{ (x(i),x(i+1), \dots , x(i+r)) : i \in \mathbb{Z} , r \in \mathbb{N} \}$, where $x(i)$ is the $i^{th}$ coordinate. $S(x)$ denotes arbitrary $\{0,1\}$ $r$-tuples such that it matches a segment of $x$.

Find a sequence $\{ y_{n} \} \subseteq \{0,1\}^{\mathbb{Z}}$ such that $S(y_{1}) \supsetneq S(y_{2}) \supsetneq \dots \supsetneq S(y_{i}) \supsetneq S(y_{i+1}) \supsetneq \dots$

The idea I had was to consider $y_{1}$ such that $y_{1}$ only contains streaks of $1$'s with prime length. Then I could define $y_{2}$ such that it avoids a particular prime length.

Community
  • 1
user100101212
  • 2,066

1 Answers1

0

Rephrasing, you want a sequence of bit strings, each infinite in both directions, so that their sets of (contiguous, finite) substrings are getting strictly smaller.

Consider the alphabet $l_0 = 0$, $l_1 = 10$, $l_2 = 110$, $l_3 = 1110$, and so on. Let $x: \mathbb{Z} \rightarrow \mathbb{N}_0$ be a sequence of nonnegative integers so that every possible (finite) substring of nonnegative integers occurs; this exists, e.g., by choosing $x(i)$ to be random.* Then define $y_n$ to be the concatenation of all $l_{x(i)}$ such that $x(i) = 0$ or $x(i) \geq n$, in the order given by $x$. Then, the set of substrings $S(y_n)$ of $y_n$ is exactly the set of all finite bit strings with no substring $01^i0$ for $0 < i<n$. So $S(y_1) \supsetneq S(y_2) \supsetneq \cdots$ as desired.

*If $X$ is a random variable with support $\mathbb{N}_0$, e.g., Poisson, and $X_i$ iid samples from $X$ for $i \in \mathbb{Z}$, then with probability $1$ every substring occurs in $(X_i)$.

Jair Taylor
  • 16,852
  • I'll buy that a randomly selected $x$ contains each possible substring of integers with probability 1, but it's not so obvious it contains all possible substrings simultaneously with probability 1. I would just say the number of finite strings of integers is countable, so they can all be appended in some order. If that cardinality needs to be proved, a technique similar to the usual $\mathbb{Z} \times \mathbb{Z} \to \mathbb{N}$ enumeration will help. – aschepler May 05 '20 at 00:31
  • @aschepler An infinite, random string would work. But sure, an explicit enumeration would work as well. – Jair Taylor May 05 '20 at 00:59