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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun