Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \subset x,\ \sigma \sigma \sigma \not \subset x$). Here $\subset$ denotes "substring" which should be distinguished from "initial segment" which I'll denote by $\sqsubset$ if the need arises.

So let $C \subset 2^{\omega}$ be the subset of Cantor space consisting of all cube-free sequences. It's uncountable, and easily seen to be closed, hence it contains a perfect set.

Question 1. Is $C$ perfect?

Let's define:

$T_C = \{ \sigma \in 2^{<\omega} : (\exists x \in C)(\sigma \sqsubset x)\}$
$\ \ \ \ \ = \{ \sigma \in 2^{<\omega} : (\forall n > |\sigma|)( \exists \tau \in 2^n )(\sigma \sqsubset \tau,\ \tau$ cube-free$)\}$
$T_P = \{\sigma \in 2^{<\omega} : (\forall \tau \sqsupset \sigma, \tau \in T_C)(\exists \rho_1, \rho_2 \sqsupset \tau$ both in $T_C)(\rho_1 \perp \rho_2)\}$

Question 2. $T_C$ is evidently $\Pi ^0 _1$, but is it in fact recursive?

If we let $P$ denote the maximal perfect subset of $C$ obtained by iteratively removing isolated points of $C$ until this procedure stabilizes (taking intersections at limit stages), then $P$ determines a tree which I believe would be the tree $T_P$ defined above.

Question 3. What is the complexity of the tree determined by $P$?

If $T_P$ is indeed the tree determined by $P$, then the tree determined by $P$ is at worst $\Pi ^0 _3$, but can we do better?


UPDATE: The answers are:

  1. Yes
  2. Yes
  3. Since $C$ is perfect, $P = C$ and so by the answers to 1 and 2, the tree determined by $P$ is just the tree determined by $C$, which is recursive.

I've learnt this after discussing it with Robert Shelton, one of the authors of the paper Gjergji linked to in his response below. In fact, what I've gathered is that there's a function $f$, better than being on the order of $n^2$, such that to determine whether an arbitrary finite string $\sigma$ has a cube-free infinite extension, it suffices to check whether it has one of length $f(|\sigma|)$ (where $|\sigma|$ is the length of $\sigma$). I suppose this would mean furthermore that the tree $T_C$ is not merely recursive, i.e. $\Delta_1$, but in fact $\Delta_0$.

share|improve this question
    
This will also be a question in dynamics. One can also ask what is the entropy of C? –  Nishant Chandgotia Apr 15 '11 at 7:09
    
I added the symbolic dynamics tag. –  Gjergji Zaimi Apr 15 '11 at 7:26
add comment

1 Answer 1

up vote 12 down vote accepted

I found an article of J.D. Currie and R.O. Shelton that answers the first question. "The set of k-power free words over Σ is empty or perfect".

Added: Note that Currie has a number of papers on power free words, and many of them are on the arxiv.

share|improve this answer
3  
Thanks. The article actually seems to answer all the questions I asked (possibly). Since $C$ is perfect, $T_C = T_P$ so questions 2 and 3 are equivalent. And Theorem 3.3 claims that we can effectively determine whether a finite binary string has an infinite cube-free extension. It's not clear whether this effective procedure is uniform however, and the proof of this theorem along with the definitions of some key terms appear to be in some other papers, so rather than chasing papers I emailed the authors and asked. I'll post an update if I get a response. –  Amit Kumar Gupta Apr 15 '11 at 15:12
    
After a fruitful back-and-forth with Robert Shelton, I've understood that yes, the tree $T_C$ is recursive. –  Amit Kumar Gupta Apr 19 '11 at 14:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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