the composition is highly symmetric and balanced. vocabularies are {0, 1, 0*0, 1.1, 0*.*0, 1.*.1}, all words are palindrome and each word has its complement. and of course all sentences(strings) are palindrome. a perfect symmetry. Beautiful! now that there is no doubt that MMS is a square-free infinite sequence. perhaps I can find a template for the proof in Thue's paper or other place. ^^; is it too exaggerated to say that the MMS is the missing fourth subject that Bach had abandoned? now I will call the song the "infinitely palindromic square free sequence". do you know other IPSF?

M...

PS: what happens if I left-shift the song by one? it is sure that the song is still square-free, but the palindrome property would be harmed... consider a palindrome string abcdefgfedcba. if I cut off the first character, then I must cut the tail, too. isnt it? like bcdefgfedcb, but how can we cut the tail out of an infinite string?

can you imagine an infinite symmetry? I believe that if you have a chance to hear the song playing, then you would really touch the Eternity. you would see the birth and the death simultaneously, even if you hear just the opening bars of a piece of the music because you have an organ to perceive a perpetual algorithm.

links: The Art of Fugue
http://en.wikipedia.org/wiki/The_Art_of_Fugue

-------- Original Message No.12386 --------
Subject: [theory-edge] Square-Free Sequence and Abelian Squere-Free Sequence
Date: Sat, 16 Sep 2006 15:31:02 -0000
From: "Michiro Nasu" nasu@...;
To: theory-edge@yahoogroups.com

Square-Free Sequence and Abelian Squere-Free Sequence

I was wrong saying that its impossible to make a mozu-song of 3-voices, ie, an infinite string over alphabet {a,b,c} with no 2-repetition. there existed a few methods. for example:

[SF1: Inter-zero gap length in PTM]
(1)Start with parity sequence(Prouhet-Thue-Morse, or PTM),
(2)Take the Sequence of inter-zero gap lengths in PTM is square-free:

PTM: 011010011001011010010110011010011001011001101001011010011001…
IZGL: 210201210120210201202101210201210120210121020120…

[SF2: Thue Sequence] Start with 0, apply: 0→012, 1→02, 2→1;

0
012
012 02 1
012 02 1 012 1 02
012 02 1 012 1 02 012 02 1 02 012 1
012 02 1 012 1 02 012 02 1 02 012 1 012 02 1 012 02 012 1 012 02 1 02

however [SF1] and [SF2] are essentially equivalent. in fact, replace 0↔2 in [SF1], you'll get [SF2]. the second one is due to Axel Thue [1906,1912]. it is sure that every permutations of [SF2] and shifted ones of those are also square-free. I wonder if there exist no SF sequences over a ternary alphabet other than this collection.

[SF3: Mathematical Mozu Song]
Start with PTM: exchange like 0→a, 00→b, 1→c, 11→d:

PTM:0110100110010110100101100110100110010110011010010110100110010…
MMS:adacbdbcadacbcadbdacbdbcadbdacbcadacbdbcadacbcadbdacbcadacbdb…

[SF4: From two copies of PTM]
Take two copies of PTM sequence; shift second one over by one, then code vertical pairs: a=00, b=01, c=10, d=11:

0110100110010110100101100110100110010110011010010110100110010110…
-0110100110010110100101100110100110010110011010010110100110010110…
-CDBCBACDBACBCDBCBACBCDBACDBCBACDBACBCDBACDBCBACBCDBCBACDBACBCD…

[SF3], [SF4] and [SF5] are SF sequence with 4-letters. it seems that [SF3] and [SF4] are in quite different lines as [SF3] is not an Abelian SF sequence while [SF4] looks like so, where Abelian Square-Free sequence is a sequence which does not have a word RR', R' is a permutation of R: for example ACDBACBC is an Abelian square-free word but ACBDBCAD is not.

[SF5: Ker"anen Sequence]
Ker"anen et al. [1992] showed that there exist infinite ASF sequences on 4-letters using the base string S of 85 characters:

S=abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbc dcacdcbdcdadbdcbca;

Paul Erd"os raised the question whether abelian squares can be avoided in infinitely long string [1961]. In 1970 Pleasants showed that there exists an infinite abelian square-free word over five letters. abelian squares cannot be avoided over a three letter alphabet. Indeed each word of length 8 contains an abelian square.

[SF6: Towers of Hanoi]
Shallit et al. [1994,2003] introduced a method to built infinite SF sequence with 6-letters adopting a solution of the "Towers of Hanoi": Suppose the pegs {X,Y,Z} and define 6 moves as A[X→Y], B[X→Z], C[Y→Z], D[Y→X], E[Z→X], and F[Z→Y]. then the moves of an optimal solution for infinite disks forms an infinite SF sequence.

ASF sequence is somewhat stronger than SF sequence in a sense that every ASF sequence is a SF sequence but not the converse. regretfully? our Mathematical Mozu Song is not abelian square-free as shown above. however mozu-songs (infinite square free strings) have actually aroused interest in algorithmic music, see [T. Laakso, Musical rendering of an infinite repetition-free string, 1996].

Michiro

links: A006156: Number of ternary square-free words of length n
Abelian Square-Free Dithering for Iterated Hash Functions
New Abelian Squre-Free DT0L-Languages over 4 Letters

"...square-freeness property of words is by no means trivial to prove. The tool which Thue invented for constructing square-free words, namely the concept of a repetition-free morphism, is still today a basic device in the study of avoidable patterns in words."

"Repetition-free morphisms are mappings between free monoids that preserve the repetition-freeness of words. The iteration of such a (nontrivial) morphism produces a repetition-free infinite word."

"Informally speaking, most of the characterizational results for morphisms say that in order to test the repetition-freeness of a given morphism, one has only to check whether the image words of short repetitionfree words are repetition-free."

-------- Original Message No.12385 --------
Subject: [theory-edge] A proof that Prouhet-Thue-Morse Sequence is cube free.
Date: Sat, 16 Sep 2006 08:29:42 -0000
From: "Michiro Nasu" nasu@...;
To: theory-edge@yahoogroups.com

A proof that Prouhet-Thue-Morse Sequence is cube free.

now that it comes to a well known fact that Prouhet-Thue-Mores sequence has no cubes, it may be unnecessary to prove it again. but I would like to finish my own proof.

Definition: Prouhet-Thue-Mores sequence is an infinite binary sequence S defined by the following procedure.

(1)S="0"
(2)loop: S=S~S, where ~S is the bitwise negation of S: continue

Definition: A square in a sequence S is a repetition of a subsequence X, |X|>0 like XX. A cube is a 3-times repetition of a subsequence X like XXX.

Theorem: Prouhet-Thue-Mores sequence has no cubes.

Proof of the Theorem:
it is sure that we shall use Principle of Mathematical Induction to prove the theorem. to show the fact for small steps is quite easy. but now we need some preparation for general case. hereafter we call a subsequence of PTMS in general a fragment, and a subsequence which is used to construct PTMS a segment. for example 0, 1, 01, 10, 0110, 1001,... are segments. every segments built at step n has length 2^n. as below.

#0:0
#1:01
#2:0110
#3:01101001
#4:0110100110010110
#5:01101001100101101001011001101001
#6:0110100110010110100101100110100110010110011010010110100110010110

scale-unit (A,B) are arbitrary segments pair, where B is the bitwise negation of A. of course every elements A,B of scale-unit are of length power of 2, ie 2^m. it is easy to see that any finite segment of length greater than 1 are partitioned by some scale-unit (A,B). we call such partitions of segments scales M(u=1/2^t) as below:

M(1)   =A
M(1/2) =AB
M(1/4) =ABBA
M(1/8) =ABBABAAB
M(1/16)=ABBABAABBAABABBA

let M be the infinite scale with arbitrary scale-unit (A,B) as

M=ABBABAABBAABABBABAABABBAABBABAAB…,

then every scales M(u) is a subscale of the scale M. as you see the scale M is said to be the fixed point of PTMS.

Lemma 1: [Scale Coercion, Every segment sits on some scale M(u)] For all segments S(n): if there exists(occurs) a segment X in S(n), there must be a scale M(u) over S(n) fits X to be placed, where S(n) denotes a segment of PTMS built at step n.

Proof of Lemma 1: apparent from the construction of PTMS.

Lemma 2: [Squares are in ABBA Pattern]
For all segments S(n), n≥2: if a square BB exists in S(n) then segment ABBA fits in S(n), where A is the bitwise negation of B.

Proof of Lemma 2: apparent from the PTMS construction and Lemma 1.

Lemma 3: [No Overlapping Squares]
In scale M there occurs a pattern neither ABABA or BABAB, where A is a segment and B is the bitwise negation of A.

Proof of Lemma 3: assume that there exists a pattern ABABA in some sequece. obviously AB is a segment. let it be X. then by Lemma 2 XX must be in the form YXXY, where Y=BA. this means that YXXY=BA-ABAB-BA. thus ABAB-A never occurs.

now we assume the following proposition hold at step n:

Assumption: For all segments S(i), i≤n: a fragment f in S(i) is a square f=FF if and only if fragment F is a segment.

Lenma 2 implies there exists no cube of segments in any segment S (n). consequently we only need to prove the Assumption for S(n+1) case. let S(n+1)=S(n)~S(n)=SS' and assume a fragment f is a square f=FF. if FF is in S or S', then by Assumption F is a segment and we are done. now assume the fragment FF is over the border of S and S'.

now let the first and second half-fragment be F1 and F2 respectively. ie, f=FF=F1F2. WOLOG we assume that F1 is in S and F2 is over the border of S and S'. consider the maximal segments in F1 and F2, and let them be s1 and s2. now F1 and F2 are partitioned into F1=f1s1f1' and F2=f2s2f2'. Lenma 1 coerces it to be f1=f2, s1=s2 and f1'=f2'. because otherwise F1 and F2 cannot be matching. (consider on scale M(u) with the scale-unit of length |s1|=|s2|.)

remember that we assumed that F2 is over the border. from Lenma 1 the segment s2 must be placed just before the border or just after the border. because otherwise s2 cannot be the maximal. anyway the fragments forms a sequence [..f1]-[s1]-[f1'f2]-[s2]-[f2'..], where [..] is a segment(scale-unit), |s1|=|f1'f2|=|s2|.

as previously mentioned s1=s2 and s1=s2≠f1'f2. because otherwise it comes to AA|A or AAA|.. , here | denotes the border of S and S'. in any case these patterns are prohibited. further as [f1'f2] is a segment it cannot be f1'=f2 since M(1)=AB but neither AA nor BB. f1'≠f2 follows [..f1]=B and [f2'..]=B.

consequently the segment sequence [..f1]-[s1]-[f1'f2]-[s2]-[f2'..] must be like B-A-B-A-B, while this is impossible by Lemma 3. we need not to mention further the case where f1 or f1' is null. QED.

This proof answers to our first question "Prove or disprove that Mozu number is a shrike number". The answer is of course "YES". ie, Mozu number has been proven to be a shrike number in binary form.

Michiro Nasu
email: nasu@...
URL: http://www.aya.or.jp/~babalabo/
ML: http://tech.groups.yahoo.com/group/theory-edge/

-------- Original Message No.12383 --------
Subject: [theory-edge] Mozu number aka Prouhet-Thue-Morse constant
Date: Fri, 15 Sep 2006 03:33:15 -0000
From: "Michiro Nasu" nasu@...;
To: theory-edge@yahoogroups.com

Mozu number aka Prouhet-Thue-Morse constant

Hi Klaus!

long time no see.
thanks for the refference. wonderful!

the sequence has been known by the name Thue-Morse sequence, or Prouhet-Thue-Morse sequence, and the irrational number built with the sequence is Prouhet-Thue-Morse constant.

I wrote regarding mozu-song in 3-voices,
> apparently to enumerate the variations of a song using some
> machinery is unsatisfiable. because in some finite steps
> your enumeration faces an exhaustion and would fall into a
> repetition. as far as the algorithm works as an machinery,
> it cannot overcome the difficulty. is it possible to create
> a true randomness by machine not but a pseudo randomness?
> as Roger pointed out correctly, this is surely a paradox.

and I suggested augmentation and counterpoints. these are the essence of Thue-Morse sequence, and it implies that the number is transcendental (not algebraic). in fact Thue-Morse number was found to be transcendental by K. Mahler in 1929.

The Thue-Morse sequence was first studied by P. Prouhet in 1851. Axel Thue in 1906 used it to found the study of combinatorics. the sequence was brought to worldwide by Marston Morse in 1921.

The sequence has been discovered independently many times, not always by professional research mathematicians; [for example] Max Euwe, a chess grandmaster and mathematics teacher, re-discovered it in 1929 in an application to chess: by using its cube-free property, he showed how to circumvent a rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.

very fine! although I'm writing a proof for the sequence being cube free, it seems already unnecessary... regarding the places of squares in the sequence I found a some useful fact. as you know Thue-Morse sequence consists of parts of length 2^m. we call these parts scale-unit. then we have a scale M,

M=ABBABAABBAABABBABAABABBAABBABAAB...

where A,B are scale-units. on any scale the places where a repetition AA or BB are fixed. now consider an integer sequence a(pos) which represents the places of the repetitions. it is no hard to find a(pos)={2,6,8,10,14,...}.

now let b(pos)=a(pos)/2={1,3,4,5,7,9,11,...}. you may find the sequence at A003159 of OEIS: http://www.research.att.com/~njas/sequences/A003159

the sequence b(pos) is said to be a parity alternating number sequence, where parity is (the parity of) the number of 1's in binary expansion. first 70 numbers in the sequence b(pos):

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 29, 31, 33, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 89, 91, 92, 93, 95, 97, 99, 100, 101, 103, 105

from the construction of the sequence, its not so surprising to hear that Thue-Morse constant relates to Mandelbrot set. after all with respect to the Mozu Number almost everything were studied. however I bet that the Mathematical Mozu Song was not.

It is a tiny shell in the sand half-hidden and half-appeared. MMS is an infinite sequence having no squares! really amazing.

-------- Original Message No.12379 --------
Subject: [theory-edge] Mozu Number was publicly known.
Date: Thu, 14 Sep 2006 03:20:18 -0000
From: "Michiro Nasu" nasu@...;
To: theory-edge@yahoogroups.com

Mozu Number was publicly known.

I wrote,
> I will call the number previously mentioned Mozu Number
> as it was proposed by a japanese shogi-game researcher
> mozu(shrike) at his homepage(in japanese).
> http://www.webspace-jp.com/~mozu/mozuiro/moromoro/senkou.html

mozu wrote to me and appointed out that he had read the infinite sequence of digits that we call "Mozu Number" in a book, A Guidance for Logical Shogi-Game (in Japanese) written by a Japanese mathematician Akihiro Nozaki.

Intuitively it is obvious that the Mozu Number is an irrational number which has no 3-times repetition of any segments. but I have not the rigorous proof of that yet. I've not read the book above, but perhaps the book does not contain the proof as it is a book for the game-fan.

Michiro

PS: he(mozu, formaly Mozuyama) requested me not to mention his name, but I've already written a lot of posts using it and mozu(kind of birds) is a general noun, I'm going to use the name as before.

-------- Original Message No.12375 --------
Subject: [theory-edge] Eternity in Mathematical Mozu Song
Date: Wed, 13 Sep 2006 04:34:55 -0000
From: "Michiro Nasu" nasu@...;
To: theory-edge@yahoogroups.com

Eternity in Mathematical Mozu Song

I've got a feeling that to prove that Mozu number is shrike is no hard. but now I just want to tell you much more amazing discovery with respect to the Mathematical Mozu Song.

the Mathematical Mozu Song is an infinite string derived from Mozu number by replacing each 0,00,1,11 in the number with alphabet a,b,c,d. look closely into the conversion process from a number to a string. Mozu number starts with 01. append the complement of 01 to the end of the segment, and get 0110. and so forth.

(0)0 → a(1)
(1)01 → ac(2)
(2)0110 → ada(3)
(3)0110 1001 → ada cbc(6)
(4)011010011 0010110 → adacb d bcada(11)
(5)0110100110010110 1001011001101001
   →adacbdbcada cbcadbdacbc (22)
(6)01101001100101101001011001101001 10010110011010010110100110010110
   →adacbdbcadacbcadbdacb d bcadbdacbcadacbdbcada (43)