6
$\begingroup$

Set-up: By abuse, let $\sigma$ represent both the left shift operator on infinite bi-infinite strings and the cyclic left shift operator on finite strings. (Thus, for example, $\sigma(...01\bar{0}10...) = ...10\bar{1}01...$ (in the bi-infinite case, we place a bar $\bar{ }$ over the "central" character) and $\sigma(10010) = 00101$). Also let $\tilde{A}$ represent the orbit of the string $A$ under $\sigma$ in both the finite and the infinite case. For convenience let's call $A$ an "unfolding" of $\tilde{A}$ whenever $A$ is in the equivalence class $\tilde{A}$. Now let $\{\tilde{A}_i\}_{i=1}^{\infty}$ be a sequence of equivalence classes of finite binary strings.

Suppose that, for each $i$, some unfolding of $\tilde{A}_i$ is contained as a substring of some unfolding of $\tilde{A}_{i+1}$ with at least one character on either side of it; for convenience let's call this an "embedding" of $\tilde{A}_i$ into $\tilde{A}_{i+1}$. If a sequence of embeddings has been specified, then it is possible to take the "limit" of this sequence $\{\tilde{A}_i\}_{i=1}^{\infty}$ and arrive at a bi-infinite binary string $A$.

Example 1: The sequence of strings

0 101 01010 1010101 010101010

has as its limit: $...0101\bar{0}1010...$

Example 2: The sequence of strings

1 010 00100 0001000 000010000

has as its limit: $...0000\bar{1}0000...$

Conjecture: Given $\{\tilde{A}_i\}_{i=1}^{\infty}$, any sequences of embeddings lead to the same bi-infinite binary string, up to orbits of $\sigma$. That is, any two limits of this process $A$ and $B$ are related via $\sigma^k(A) = B$ for some integer $k$.

This result would be quite surprising to me if it were true, but I have not been able to construct a counterexample. It can be made more precise using the categorical language of projective limits, but I think the question is clear enough without going through this trouble.

Improve this question
$\endgroup$
1
  • $\begingroup$ Some (partial) detail on the construction via projective limits, for those who are interested: Define the index set $I = \{[a,b)\cap\mathbb{Z} : a,b\in\mathbb{Z}\}$; this is a directed set when given the subset ordering. For $i = [a,b)\cap\mathbb{Z}$, let $X_i$ be the category of subsets of $[a,b)\cap\mathbb{Z}$, and let $f^j_i:X_j\to X_i$ be the morphism $f^j_i(S) = S\cap i$. The question can now be stated: If one quotients the $X_i$'s by cyclic equivalence, can the projective limit still be defined? $\endgroup$
    – Adam Quinn Jaffe
    Jul 5, 2019 at 13:50

2 Answers 2

Reset to default
3
$\begingroup$

The conjecture is false. Here is a counter-example:

Let $A_0:=\mathtt{11000}$ and $B_0:=\mathtt{11010}$ and recursively define \begin{align} A_{k+1} &:= B_k B_k A_k A_k A_k \;,\\ B_{k+1} &:= B_k B_k A_k B_k A_k \;. \end{align} That is, $A_n$ and $B_n$ are obtained by iterating the substitution $(\mathtt{0}\mapsto A_0, \mathtt{1}\mapsto B_0)$ on $(A_0,B_0)$. Note that $A_k$ occurs in $A_{k+1}$ in more than one positions. Note also that for each $n$, $A_n$ and $B_n$ do not overlap with each other or with themselves.

Let $x$ be the limit of $A_n$ as you described, by always choosing the central symbol as the "reference position": \begin{align} \begin{array}[ccccc]\ \mathtt{1} & \mathtt{1} & \underline{\mathtt{0}} & \mathtt{0} & \mathtt{0} \\ B_0 & B_0 & \underline{A_0} & A_0 & A_0 \\ B_1 & B_1 & \underline{A_1} & A_1 & A_1 \\ & & \vdots & & \end{array} \end{align} In other words, $x$ has the form \begin{align} \cdots\underbrace{B_2B_2\overbrace{B_1B_1\underbrace{B_0B_0\overbrace{\mathtt{11\underline{0}00}}A_0A_0}A_1A_1}A_2A_2}\cdots \end{align}

Similarly, let $y$ be the limit of (the shifts of) $A_n$ where at each level, the fourth block is chosen as the "reference block", within which the fourth sub-block is chosen as the "reference sub-block" and so forth: \begin{align} \begin{array}[ccccc]\ \mathtt{1} & \mathtt{1} & \mathtt{0} & \underline{\mathtt{0}} & \mathtt{0} \\ B_0 & B_0 & A_0 & \underline{A_0} & A_0 \\ B_1 & B_1 & A_1 & \underline{A_1} & A_1 \\ & & \vdots & & \end{array} \end{align} In other words, $y$ has the form \begin{align} \cdots\underbrace{B_2B_2A_2\overbrace{B_1B_1A_1\underbrace{B_0B_0A_0\overbrace{\mathtt{110\underline{0}0}}A_0}A_1}A_2}\cdots \end{align}

This may look different from your procedure of first doing cyclic shifts and then taking the limit of centered strings. The limits are however the same.

Claim: $y$ cannot be a shift of $x$.

Argument: Suppose that $y=\sigma^m x$ for some $m\in\mathbb{Z}$. Clearly $m\neq 0$. Let $n$ be such that $|A_n|=|B_n|>|m|$. Observe that both $x$ and $y$ admit unique decompositions into blocks $A_n$ and $B_n$. The uniqueness is because $A_n$ and $B_n$ are non-overlapping. Since $y=\sigma^m x$, the decomposition of $y$ must be the shift of the decomposition of $x$ by $m$. But this would require $m$ to be a multiple of $|A_n|=|B_n|$, contradicting the choice of $n$. $\Box$

Remark: By arbitrarily choosing the third or the fourth occurrences of $A_k$ in $A_{k+1}$ as the "reference" one, we find that there are uncountably many distinct limits no two of them are shifts of each other. I feel that this must be a special case of a standard fact about substitutions, but I am not an expert.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Your remark is almost true. Certainly we get uncountably many different sequences in this way (assuming the substitution is primitive and recognisable, so the associated subshift is aperiodic). If two sequences of 'choices' are eventually equal, then they describe elements which are shifts of one another. There are a few other boundary cases where elements can be shifts of one another without being eventually equal in their sequence of choices, and these are described by the Vershik map on the associated Bratelli diagram in the case where one 'carries' in the addition/shift $\endgroup$
    – Dan Rust
    Jul 8, 2019 at 0:36
  • $\begingroup$ - or if you prefer using the terminology of supertiles, it's the cases of where two infinite-level supertiles meet, one being described by choices always eventually falling to the left, and one eventually always to the right. I think there is a small mistake in your argument however, as you're assuming that the level-$n$ decompositions of both elements are lined up, and that is not necessarily the case. $\endgroup$
    – Dan Rust
    Jul 8, 2019 at 0:36
  • $\begingroup$ You can fix the argument by just noting that the subshift associated with an aperiodic substitution is uncountable, and each element of the subshift can be described uniquely with a sequence of 'choices', whereas each shift-orbit is countable. The proof that the subshift is uncountable follows from the aperiodicity of elements and their uniform recurrence (or minimality of the subshift). $\endgroup$
    – Dan Rust
    Jul 8, 2019 at 0:36
  • $\begingroup$ Thank you @DanRust I knew there must be a more standard argument. For the remark, however, I still think that the particular procedure (with arbitrary choices of the 3rd or the 4th occurrences at each level) gives distinct sequences which cannot be shifts of one another because of the non-overlapping property. Note that the iteration is not by substitution, but by extension to larger and larger supertiles. $\endgroup$
    – Algernon
    Jul 14, 2019 at 15:30
  • $\begingroup$ I didn't catch what you meant by my assumption regarding the level-$n$ decomposition. What exactly are you referring to? $\endgroup$
    – Algernon
    Jul 14, 2019 at 15:32
0
$\begingroup$

You do not need to take the cyclic shofts: the conjecture is false even without them.

Assume that $A_i$ can be embedded into $A_{i+1}$ in two ways. Then you will get $2^\omega$ possible limits; so, if they are all distinct, then you cannot hope they are in the same class. Moreover, you will get oncountably many classes.

For a concrete example, one can set $A_{i+1}=0A_i1A_i0$. If $A_i$ is embedded into $A_{i+1}$ in two different ways, its surrounding looks different, so the limits are different as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.