3
$\begingroup$

Let $\Sigma$ be a subshift of finite type (SFT) with the alphabet $\{0,1\}$, which is given by the set of forbidden words $\mathcal F$, all of length $N$.

Question. Is there a $\delta>0$ such that for any such $\mathcal F$ of cardinality at most $\delta 2^N$, the topological entropy of $\Sigma$ is positive? If so, what is the best known value of $\delta$?

(This question may be seen as a follow-up of The spectral radius of a binary matrix - polynomial growth?. The incidence matrices one gets when converting an SFT into a topological Markov chain via the standard procedure (see, e.g., http://math.uchicago.edu/~may/REU2014/REUPapers/So.pdf) come out very sparse for large $N$, so the criterion given in the answer doesn't appear to apply.)

$\endgroup$
7
  • 1
    $\begingroup$ Related: the work of McGoff and Pavlov on random SFTs. They say: if you include each word of length $N$ with probability $p$, what can you say about the entropy of the resulting SFT. $\endgroup$ – Anthony Quas May 11 '17 at 19:23
  • $\begingroup$ Thanks, Anthony. I have found projecteuclid.org/euclid.aop/1332772716 and will have a look at it. Said that, I'm more interested in the worst case scenario rather than a random one. $\endgroup$ – Nikita Sidorov May 11 '17 at 19:32
  • $\begingroup$ So I guess the McGoff paper shows that if $\delta<\frac 12$, then the topological entropy is not forced to be positive; and you might guess that if $\delta>\frac 12$, then the topological entropy is forced to be positive. An explicit example with $|\mathcal F|=2^{n-1}$ and 0 entropy is $\mathcal F$ is the collection of words with an even number of 1's. $\endgroup$ – Anthony Quas May 11 '17 at 20:35
  • $\begingroup$ There are examples with $\delta<0.1$ and zero entropy. Probably, even with $\delta<0.05$, although this needs to be double-checked. $\endgroup$ – Nikita Sidorov May 11 '17 at 20:57
  • 1
    $\begingroup$ Sorry. My $\delta$ is one minus your $\delta$! $\endgroup$ – Anthony Quas May 11 '17 at 21:31
2
$\begingroup$

Here's a heuristic suggesting that maybe something like $2^N/N$ forbidden words could be enough to give 0 entropy:

Consider $N$-step transitions between blocks of length $N$. That is: if $L_N$ is the set of all words of length $N$, you're asking: for which $U,V$ in $L_N$ is the concatenation $UV$ legal.

Clearly in the full shift, every transition between $N$-blocks is legal, that is, there are $2^{2N}$ such legal transitions. When a word of length $N$ is forbidden, I want to count the number of $N$-block transitions that are excluded, if the word $W$ is excluded. That is, I want to count the number of pairs $(U,V)$ such that the concatenation $UV$ contains the block $W$. There are $N+1$ locations in a block of length $2N$ where a $W$ could appear; and each one of them rules out $2^N$ possible transitions, as the remaining symbols can be filled in in any way. That is: a forbidden $N$-word, $W$, gives rise to $(N+1)2^N$ forbidden transitions between $N$-blocks (of course if there are repetitions then it may be smaller than this). Now, forbidding something like $2^N/N$ words, assuming that these forbidden words can be chosen very carefully with minimal overlaps might be enough to rule out all of the $2^{2N}$ transitions.

For a bound in the other direction, notice that if you forbid $\alpha 2^N/N$ words with $\alpha<\frac 12$, then the crude bounds that I gave rigorously show that there are at least $(1-\alpha)2^{2N}$ transitions remaining. This is sufficient for positive entropy by the criterion in the answer to your previous post.

$\endgroup$
1
  • $\begingroup$ For what it's worth, I'm hoping someone gives a better answer than this one. $\endgroup$ – Anthony Quas May 12 '17 at 15:36
3
$\begingroup$

There's a related notion of "unavoidable sets of words"; a set $S$ is unavoidable if every sequence on $\{0,1\}$ includes a subword in $S$. Put another way, $S$ is unavoidable if the SFT you define above is the empty set.

The asymptotics of the minimal size of an unavoidable set of $n$-letter words is known to be $2^n/n$ as Anthony conjectured. I think this was first proved in "On the Synchronizing Properties of Certain Prefix Codes" by Schutzenberger, from 1964.

This definitely implies that removing roughly $2^n/n$ words is enough to get down to the empty set, and so certainly to a shift of entropy 0. In theory, it could be the case that you could remove significantly fewer n-letter words and get to a non-trivial zero-entropy subshift, but Anthony's argument seems to show that using fewer than $(0.5)2^n/n$ leaves positive entropy. This seems to show that the proper version of your original question is to consider $\delta 2^n/n$ instead of $\delta 2^n$; then $\delta = 1/2$ seems to work, but $\delta = 1$ definitely doesn't. I would expect that all $\delta < 1$ would suffice, but am not sure about this.

As Anthony referenced, McGoff's work shows that if you are willing to deal with a very low probability (approaching $0$ as $n \rightarrow \infty$) of ending up with a zero-entropy subshift, then removing a random set of n-letter words of size $\delta 2^n$ for any $\delta < 1/2$ works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.