3
$\begingroup$

In a comment made by Gjergji Zaimi to this older question, it is conjectured that $\frac 73$ is the threshold separating countability and uncountability of the sets of infinite binary words having a given critical exponent. In a later comment, James Currie cites the (remarkable!) paper:

"J. Karhumaki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory. Ser. A 105 (2004), 335–347."

as the one proving the conjecture. Is it so, though?

In general, it is not true that, if every element of $S\subset\{0,1\}^\omega$ has at most polynomially many finite subwords of length $n$, then $|S|\le \aleph_0$. In fact, it is sufficient to allow $n+1$ subwords of length $n$ to get an uncountable set, as exemplified by the well-known Sturmian words. So the conjecture ie either false or there must be a more specific argument involving critical exponents to establish the conjecture. What is it?

$\endgroup$
5
  • 3
    $\begingroup$ In the paper "The ubiquitous Prouhet-Thue-Morse sequence", Allouche and Shallit claim that there are uncountably many overlap-free binary words, which implies that the threshold is 2. I believe this follows from Fife's theorem. $\endgroup$
    – BPP
    Sep 14, 2021 at 21:26
  • $\begingroup$ Of course! I knew the paper...just forgot it :) Thanks. $\endgroup$ Sep 14, 2021 at 21:30
  • $\begingroup$ So @Ben's comment answered the question? $\endgroup$ Sep 15, 2021 at 0:18
  • $\begingroup$ @Bjørn Kjos-Hanssen Yes. $\endgroup$ Sep 15, 2021 at 6:48
  • $\begingroup$ A simple proof of uncountability of binary words with critical exponent 2, based indeed on Fife's theorem, is here: cs.uwaterloo.ca/~shallit/narad_phd.pdf (2.14-2.16) $\endgroup$ Sep 15, 2021 at 7:21

1 Answer 1

1
$\begingroup$

[From user Ben's comment]

In the paper "The ubiquitous Prouhet-Thue-Morse sequence" (DOI link behind paywall, preprint version), Allouche and Shallit claim that there are uncountably many overlap-free binary words, which implies that the threshold is 2. I believe this follows from Fife's theorem.

$\endgroup$

Your Answer

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

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