Re: [math-fun] Gap sequences for Thue-Morse
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
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
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. 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
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
Oops, I am very sorry, I mistyped the Walnut command. It should be 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))": and not as I wrote previously.
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)":
"Walnut" has spoken ... impressively in its own inscrutable fashion, but at the same time failing to offer insight into _why_ the result is true --- not that my own tedious effort constitutes a significant improvement in this respect! Of course, there is a shifting cultural background to such criticism. Nowadays I am perfectly content to accept Maple's evaluation of a knotty integral, without demanding an explanation of the (probably impenetrable) chain of reasoning by which it was arrived at! WFL On 2/25/17, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
Oops, I am very sorry, I mistyped the Walnut command. It should be
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))":
and not as I wrote previously.
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)":
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
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
participants (2)
-
Fred Lunnon -
Jeffrey Shallit