now I want to give a brief summary for the threads began on Sep 7.




Questions and Answers:

Q1: Show the proof of binary Mozu number(aka PTM) is cube-free.

it was done by using *scales*. I'm not satisfied with the solution,
as it can be redefined with an endomorphism like below.

Definition: PTM is an infinite string over {A,B} generated
with morphism M: {A,B}*->{A,B}* such that A->AB and B->BA.

Q2: Are there any other binary cube-free sequences than PTMs?

PTMs means a collection of sequences: the PTM, the complement
of PTM, and the left-shifted ones of those. it is still open, but
considering the above morphism, if there exists one then it might
be artificially devised one like g85 SF sequence over 4-letters.

Q3: If S is an infinite square-free binary sequence, then also
the complement of S, and arbitrarily left-shifted ones are.

intuitively self-evident. and it follows that if there exists
one then there exist infinite number of such sequences.

Q4: Show the proof that Mathematical Mozu Song is square-free.

unfinished. but after that we've got the morphism for MMS, it is
no more a hard problem (as same problems are solved earlier).

Q5: Are there any other square-free infinite sequences than MMS?

yes. Thue sequence, Divest sequence, Ker"anen sequences, etc are
known. the first is over 3-letters and the rest two are 4-letters.
as well 5 and 6-letter sequences are devised.

Q6: Are there square-free infinite sequences over 3-letters?

yes. Thue sequence is the one. Q6': Are there any other ternary
square-free sequences than Thue sequence(s)? may be still open.

Q7: Whether MMS number is square-free even in 3-base system or not?

very unlikely. but worth to check.

Q8: Are there any other palindromic square-free sequence than MMS?

unknown. PTM(2-letters) is not palindromic but somewhat symmetric
as the right-half is the negation of the left-half. Thue sequence
(3-letters) lacks any symmetry.

Q9: Show that if N is a square-free irrational number in b-base
system, then for all b'>b: N is also square-free in b'-base system.

intuitively true. leave for the readers.

Q10: Any infinite repetition-free sequence is able to construct
with a morphism.

I add this question here. it is raised from the quote (and also
from some of my experience) by Veikko Ker"anen stating:

"...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."

Paraphrased: Are all infinite repetition-free sequences *fractal*?

Q11: Show that there exist many other abelian square-free sequences
over 4-letters between Divest sequence and Ker"anen sequence.

This question slightly relates to the open questions below given
by Divest. refer to the link at the bottom.

Divest(2): Does ASF(abelian square free) really add anything over SF?
Divest(3): Are there generalizations of ASF that could be used?

M...

this thread begins at:
http://tech.groups.yahoo.com/group/theory-edge/message/12336
and the main branch is:
http://tech.groups.yahoo.com/group/theory-edge/message/12348

Links: Abelian Square-Free Dithering for Iterated Hash Functions
http://csrc.nist.gov/pki/HashWorkshop/2005/Nov1_Presentations/rivest-
asf-paper.pdf#search=%22square%20free%20sequence%22

New Abelian Squre-Free DT0L-Languages over 4 Letters
http://south.rotol.ramk.fi/keranen/ias2002/NewAbelianSquare-FreeDT0L-
LanguagesOver4Letters.pdf#search=%22square%20free%20sequence%22

http://tech.groups.yahoo.com/group/theory-edge/message/12397

-----------------------------------------------------------------------
a trivial proof of Q3


> Q3: If S is an infinite square-free binary sequence, then also
> the complement of S, and arbitrarily left-shifted ones are.
>
> intuitively self-evident. and it follows that if there exists
> one then there exist infinite number of such sequences.

Proof of Q3: the complement case is self-evident as the letters
are just abstract symbols. let S be an infinite square-free binary
sequence, and assume S=pS' and S' is not square-free, where p is a
partial string of S. then evidently S is not square-free because S
contains the repeating part of S'. contradiction.

now suppose S and S' are infinite square-free sequence and S=pS',
where p is a non-trivial partial string. assume S=S', then
S=pS'=pS=ppS'. thus S is not square-free. contradiction. therefore,
S=/=S'. this implies that every left-shifted sequences are not equal
to S and there exist infinite number of different such sequences.

Q3 is true for any infinite k-repetition free sequence over
m-letters as far as left-shift is made by character-base. with
regard to *complement*, read it *permutation*.

http://tech.groups.yahoo.com/group/theory-edge/message/12400