So here is how to prove your assertion about the Thue-Morse sequence "purely mechanically", that is, using the theorem prover Walnut written by Hamoon Mousavi. First, download Walnut from my web page: https://cs.uwaterloo.ca/~shallit/linz/walnut-for-linz.zip and install it on your machine. Next, go to the directory "Word Automata Library" and copy the file T.txt and call it S.txt. Then edit the content so it looks like this: msd_2 0 0 0 -> 0 1 -> 1 1 1 0 -> 2 1 -> 0 2 2 0 -> 2 1 -> 3 3 1 0 -> 0 1 -> 2 This is our representation for an automaton for your sequence S. S accepts n written in base 2, msd first, and returns S[n] (starting at index 0). Next, go to the "bin" directory and type "Java main.prover". Then enter the following command eval lunnon "An ((T[n]>T[n+1])=> S[n]=@2)&((T[n]=T[n+1)=>S[n]=@1)&((T[n]<T[n+1])=> S[n]=@0)": which is just the first-order expression of your claim that S[n] = 1 + t[n] - t[n-1] translated a bit. Note that "An" means "for all n". After a very brief delay, the program will create a file called "lunnon.txt" which has the single word "true" in it. 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun