Date: 2017-02-25 07:59 From: Jeffrey Shallit <shallit@uwaterloo.ca> To: <math-fun@mailman.xmission.com>, Fred Lunnon <fred.lunnon@gmail.com> Reply-To: shallit@cs.uwaterloo.ca, math-fun <math-fun@mailman.xmission.com> Some history: Thue actually *defined* his squarefree sequence 210201... by counting the number of 1's appearing between consecutive occurrences of 0 in (what we now call) the Thue-Morse sequence t. From the fact that t is overlapfree, a very very simple argument shows that the resulting sequence is squarefree. (For example, it appears in my book, A Second Course in Formal Language Theory.) The same argument applies to counting the number of 0's between consecutive 1's. So in some sense, you are doing it backwards. It is easiest to start from the overlapfreeness of Thue-Morse, and from this derive the squarefreeness of the resulting sequence. In any event, both the squarefree property of 210201... and 012021... is easily proved ab initio using the "logical approach" I have described in a number of papers (see my home page). For this, you need to find an automaton generating these sequences, and this is pretty easy, too. The first sequence is generated by iterating the morphism 2 -> 210 1 -> 20 0 -> 1 and the second is generated by iterating the morphism 0 -> 012 1 -> 02 2 -> 1 Both of these are pretty easy to prove by induction. <End JS> There's some sort of equivalence between the gaps method and direct conversion of Thue-Morse. E.g., starting with 0, the 5th iteration of your second morphism produces In[576]:= NestList[StringReplace[#, {"0" -> "012", "1" -> "02", "2" -> "1"}] &, "0", 5] Out[576]= {"0", "012", "012021", "012021012102", "012021012102012021020121", "012021012102012021020121012021012102012101202102"} But here is a piece of Thue-Morse base 4: In[577]:= "112122112212112122121122112122112212112211212212"; Shifting right one bit, In[580]:= IntegerString[FromDigits[%577, 4]/2, 4] Out[580]= "23031023103023031030231023031023103023102303103" Changing 2 to 1 and 3 to 2, In[581]:= StringReplace[%, {"2" -> "1", "3" -> "2"}] Out[581]= "12021012102012021020121012021012102012101202102" is your 5th iterate, modulo a dropped leading 0. --rwg On 2/24/17 9:38 PM, Fred Lunnon wrote:
A month ago I mentioned the sequence of gaps between consecutive occurrences of 1 in the Thue-Morse sequence, which rather prettily appeared identical to the well-known classical example of a `square-free' ternary sequence:
[S_n] = 0 1 2 0 2 1 0 1 2 1 0 2 0 1 2 1 ... ,
in turn related to Thue-Morse = (sum of binary digits of n ) mod 2 ,
[T_n] = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ... ,
via S_n = 1 + T_n - T_{n-1} .
At the time I assumed there existed some obvious, easily-discovered explanation of the identity. While that may well be the case, I haven't succeeded in discovering any: it is doubtful whether my present proof, hewn from granite over several days of tantalising head-scratching, could be compressed to less than a page while remaining intelligible.
So is it obvious --- even if it isn't obviously obvious? WFL [25/02/17]
On 1/22/17, Fred Lunnon <fred.lunnon@gmail.com> wrote:
For case w = 1 , the resulting gap sequence is apparently the standard square-free ternary sequence S_n = 1 + T_n - T_{n-1} , with T_n denoting Thue-Morse sequence.
This is indeed an "automatic sequence" in the sense of Allouche & Shallit's book of that title (2003), and generated by the width-4 iterated morphism 0 -> 03, 1 -> 02, 2 -> 21, 3 -> 20 followed by terminal symbol-to-symbol encoding 3 -> 1 . If I have understood JS correctly, it follows that both other cases w = 01, 010 are also automatic sequences, and so generated in a similar fashion.
How wide are their morphisms? An ominous feature of the recursions I found earlier is the division by 3 rather than 2 involved in computing n" , suggesting that the width must be at least 6 ; if the same morphism also serves case w = 0 (and 1), the width goes up to at least 12 .
WFL
On 1/21/17, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
I just want to point out that there is a technology that can answer questions like this purely mechanically, by a machine computation. Given any particular w, or even for all w of a given length, the gaps between occurrences are specified by a finite automaton, which can be computed "automatically". We can also produce a so-called "linear representation" that specifies gap positions and/or their first differences. See the papers on my home page, particularly E. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable properties of automatic sequences, Int. J. Found. Comput. Sci., 23 (2012), 1035-1066.
Jeffrey Shallit https://cs.uwaterloo.ca/~shallit/papers.html
On 1/21/17 9:26 AM, Fred Lunnon wrote:
As an indirect result of contemplating Jim Propp's Mathematical Enchantments
https://mathenchant.wordpress.com/2017/01/16/avoiding-chazakah-with-the-prou...
I became distracted (the way one does) into examining the sequence of gaps between repetitions of a given word w in the Thue-Morse sequence.
Obviously the gap sequence will vary according to w . But it turns out that every such sequence is related by linear transformation and index shift to one of just three particular cases: w = 0, 01, 010 --- see for example sect. 4 of Lubomira Balkova, Edita Pelantov a, Wolfgang Steiner "Return words in the Thue-Morse and other sequences"
https://hal.archives-ouvertes.fr/file/index/docid/90970/filename/BPS.pdf
Initial segments, compressed into infinite words --- Thue-Morse: 01101001 10010110 10010110 01101001 10010110 01101001 01101001 10010110 ... Gaps w = 0 : 21020121 01202102 01202101 21020121 01202101 21020120 21020121 01202102 ... Gaps w = 01 : 11201102 11202110 11201102 11011202 11201102 11202110 11202112 01102110 ... Gaps w = 010 (halved): 21032301 21030123 21032301 23210301 21032301 21030123 21030121 03230123 ...
From case w = 0 , the gap sequence for w = 1 follows by transposing 0 with 2 : which may be considered linear S_n -> 2 - S_n , or else the limit of shifts n -> n + 2^k for k = 0,1,2,... Either way, the result commences 0 1 2 0 2 1 0 1 2 1 0 2 0 1 2 1 ... 'Ang abaht --- < = > < > = < = > = < > < = > = ... --- haven't we seen something very like this somewhere else recently?
So it would be reasonable to expect the other two cases to have
some
simple relation to Thue-Morse as well. Yeah, right --- the most concise (conjectural) recurrences I have been able to come up with for S_n so far are the following horrors.
Given index n > 0 , for 0 < n <= 8 , set explicitly S_1,...,S_8 = 1, 1, 2, 0, 1, 1, 0, 2 for w = 01 , 2, 1, 0, 3, 2, 3, 0, 1 for w = 010 ; define k, n', n" via 4 n' < n <= 8 n' = 2^k ; n" = (n' - (-1)^k)/3 for w = 01 , (n' + 2(-1)^k)/3 for w = 010 ; then for n > 8 , S_n = S_(n - 4*n') for 4 n' < n <= 6 n' , S_(n - 3*n' + n") for 6 n' < n <= 7 n' , S_(n - 5*n' + n") for 7 n' < n <= 8 n' .
Fred Lunnon
_______________________________________________