But that is easy, I typically assign this as a problem in my 4th year formal language theory course. I'll send you the solution by a separate e-mail, without clogging the rest of the list. On 2/25/17 11:31 AM, Fred Lunnon wrote:
Pertinant --- but doesn't completely solve the problem, which then resolves to showing that S' defined by your second morphism 0 -> 012 , 1 -> 02 , 2 -> 1 is the same sequence as S defined by my (corrected, groan!) S_n = 1 - T_n + T_{n-1} .
WFL
On 2/25/17, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun