6
$\begingroup$

Let $\omega$ denote the set of non-negative integers. For which integers $n>1$ is there a sequence $b_n: \omega\to\omega$ with the following property?

Whenever $v\in\omega^n$ there is a unique $i_v\in\omega$ such that for all $j\in\{0,\ldots,n-1\}$ we have $v(j) = b_n(i_v+j)$.

$\endgroup$
3
  • 3
    $\begingroup$ I think $n=2$ works with $b_2 := 010212031323041424340515253545061\dots$ $\endgroup$ Commented Oct 26 at 20:26
  • 3
    $\begingroup$ There is. Order $\omega^n$ lexicographically. Start with $n$ zeros. At $k$-th step choose the least $v\in\omega^n$ that hasn't been used. Add $n$ pairwise different symbols that haven't appeared yet to the existing word (separators). Build $v$ after separators. Go to step $k+1$ $\endgroup$
    – te4
    Commented Oct 26 at 22:36
  • $\begingroup$ Nice, can you post this as an answer so we can close this thread? $\endgroup$ Commented Oct 27 at 9:00

1 Answer 1

5
$\begingroup$

$\newcommand\N{\mathbb N}$For every $n\ge1$ there is such sequence $b_n$. I replace $\omega$ with $\N$. Endow $\N^n$ with any total order $<$. Let $b_{n,0}$ consist of $n$ zeros. For $k\in\N$ let $v=v_k$ be the minimal element of $\N^n$ that hasn't appeared in $b_{n,k}$. Take $n$ elements $l=l(k)=(l_1,\ldots,l_n)$ of $\N$ that are not in the finite sequence $b_{n,k}\cup v$ and let $b_{n,k+1}$ be concatenation of $b_{n,k}$, $l$ and $v$. Every subsequence of $b_{n,k+1}$ of length $n$ is either in $b_{n,k}$, or overlaps with $l$ (and then, by construction of $l$, can be uniquely determined by length of its $l$-head/$l$-tail), or is $v$. Therefore, for every $k\in\N$, $v\in\N^n$ there is at most one such $i_v$. By construction, for every $v\in\N^n$, for all large enough $k\in\N$, $k>k_v$, there is at least one such $i_v$. Thus, one may take $b_n=\lim_{k\to\infty}b_{n,k}$.

$\endgroup$
1
  • 3
    $\begingroup$ Excellent. Let's add that the total order needs to be of order type $\omega$. For example the lexicographic total order $(0,0)<(0,1) < (0,2) < \dots < (1,0) < (1,1) < \dots$ for $n=2$ is not of order type $\omega$ and it is never going to exhibit $(1,0)$. On the other hand the total order $(0,0) < (0,1) < (1,0) < (1,1) <$ $(0,2) < (1,2) < (2,0) < (2,1) < (2,2) <$ $(0,3) < (1,3) < (2,3) < (3,0) < (3,1) < (3,2) <(3,3) <$ $(0,4) < \dots$ works. It yields the sequence $b_2 = 0,0,2,3,0,1,4,5,1,0,6,7,1,1,8,9,1,2,\dots$ $\endgroup$ Commented Oct 27 at 11:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .