Now, for any n, thereĮxist k and 1 ≤ j < g ( k ) so that j h ( k ) ≤ n < ( j + 1 ) h ( k ).įor every point of x, there exists σ of length k so that x We denote h ( k ) = ∏ k − 1 i = 0 g ( i ) for all k. Of length k, every word a σ, b σ has length between ∏ k − 1 i = 0 g ( i ) and It remains to bound c n ( X ) from above. Then consider the n-letter subwords of x i defined by u j = x i ( − j ) ... x i ( n − j − 1 )įor 2 M ≤ j 4 M, c n ( X ) > k ( n − 2 M ) + m ( n − 2 N ), and so by weak linear complexity of X X i ( 1 ) ... x i ( n ) does not contain v i and is immediately preceded or followedīy v i we treat only the former case, as the latter is trivially similar. Without loss of generality (by shifting if necessary), assume that Otherwise, there exists an n-letter subword of x i not containing v i. The assumption that X contains at least t orbits of non-recurrent points was then false, completing the proof. Therefore, lim inf c n ( X ) − t n > − ∞, contradicting weak linear complexity of X with index t. Now, for any n > 2 N, define the following words in L n ( X ): v i, m = x i ( m ) … x i ( m + n − 1 ) for 1 ≤ i ≤ t and N − n 2 N. By shifting the x i and/or extending the w i if necessary, we may also assume that there exists N so that x i ( − N ) … x i ( N ) = w i for each i. We know that this is false, and so have a contradiction, implying that w k can be extended to a longer subword of x k for which the desired property holds.īy earlier observations, since j ≠ k were arbitrary, we may now assume without loss of generality that w i appears exactly once in x i for each i, and that for all j ≠ k, either w j is not a subword of x k or w k is not a subword of x j. Since w k appears exactly once in each of x j and x k, this would mean that for every n, the n letters preceding and following w k are the same in x j and x k, and so that x j is just a shift of x k. every subword of x k containing w k also appears in x j. Suppose for a contradiction that this is not the case, i.e.
![subshift disjoint from a given subshift subshift disjoint from a given subshift](https://miro.medium.com/max/1996/1*nhjsEkBNTMsXygRkUDeHxg.png)
We claim that w k can then be extended to a larger subword of x k which does not appear in x j at all.
![subshift disjoint from a given subshift subshift disjoint from a given subshift](https://www.math-only-math.com/images/VENN_DIAGRAMS-b.jpg)
The only remaining case is that w k appears exactly once in x j. Then, the desired property could be obtained by extending w j to this larger word. Similarly, if w k appears at least twice as a subword of x j, then x j contains a subword containing w j and two occurrences of w k, which itself cannot be a subword of x k since w k appears only once in x k. If w k is not a subword of x j, then the desired property already holds.