[seqfan] Re: help needed with former sequence A138036

[franktaw at netscape.net]

I poked around the net a bit, and found: 
http://www.springerlink.com/content/73513536720r8807/, a paper by 
Veikko Keranen titled "Abelian Squares are Avoidable on 4 letters. This 
is a subscriber-only site, so I was unable to see the actual article.

There are some sequences that should probably be present here. 
According to the abstract, Keranen (there should be an umlaut on the 
"a") gives a specific example, which should be included with a->1, 
b->2, c->3, d->4. Also, we ought to have the number of 4-symbol Abelian 
squarefree sequences of length n, both unrestricted and normalized 
(i.e., starting with 1, with a 2 before the first 3, which is in turn 
before the first 4).

Franklin T. Adams-Watters

-----Original Message-----
From: franktaw <franktaw at netscape.net>

Hugo left out a key word in his abbreviation of the text:
    ... Abelian squares are unavoidable ...

I think "Abelian square" means that the word has the form XABY, where A
and B contain the same non-empty multiset of letters; then the AB are
an Abelian square.

What this has to do with the sequence I don't know.

Question: does every sufficiently long string over a finite alphabet
contain an Abelian square in this sense? (Note that, since there are
only finitely many choices at each step, the existence of arbitrarily
long squarefree sequences implies the existence of an infinite such
sequence. (The reverse is trivial, of course.))

Franklin T. Adams-Watters

-----Original Message-----
From: hv <hv at crypt.org>

I don't speak Mathematica; by eye, the first list looks like all
square-free sequences in a 3-symbol alphabet ordered first by length,
then lexically.

Looking back at the history, it seems to be a demonstration of this:

  [T]his computation shows that [...] squares are unavoidable over
  3 letters, since every word of length 8 turns out to contain them.

.. unfortunately swaddled in so much semi-mystical verbiage as to be
effectively encrypted.

Replacing the mysticism with a clear explanation would probably be
sufficient to make this worth keeping.

Hugo


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/