Subshifts of finite type of guaranteed positive entropy

Question

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.)

Answer 1

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.

Answer 2

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.