Toistovapaat Merkkijonot
Norjalainen matemaatikko Axel Thue [7] (1863-1922) aloitti sanojen rakenteita koskevan systemaattisen tutkimuksen vuosisatamme alussa. Hänen perustavanlaatuisille tuloksilleen, jotka koskevat annetusta aakkostosta muodostettavissa olevia äärettömiä toistovapaita eli säännöllisyyksiä välttäviä sanoja, on löydetty useita sovellutuksia matematiikan eri aloilta. Toistovapaat sanat ovat äskettäin herättäneet mielenkiintoa myös musiikin alalla, ks. Laakso [5].
Olkoon X nelikirjaiminen aakkosto {a,b,c,d }. Raportissa [3] (Keränen 1992) esitimme tietokoneen avulla löydetyn Abelin neliöistä vapaan endomorfismin g: X* -> X* (kuvauksen joka säilyttää sanojen toistovapauden), jonka koko on |g(abcd)| = 340. Endomorfismi g määritellään seuraavasti. Kirjaimen a kuvasana on
ja muiden kirjainten b, c, d kuvasanat g(b), g(c), g(d) saadaan syklisellä permutaatiolla edeltävistä sanoista g(x), missä kirjain x kuuluu aakkostoon X.
Kaikki tällä hetkellä tunnetut menetelmät, ks. [1] (Carpi 1994), rajoittamattoman pituisten Abelin neliöistä vapaiden sanojen konstruoimiseksi aakkostossa X perustuvat tämän endomorfismin g rakenteeseen. Kuitenkaan ei tiedetä, onko aakkostossa X mahdollista määritellä Abelin neliöistä vapaita endomorfismeja, joiden koko olisi pienempi kuin yllämainittu koko 340. Tämän kysymyksen ja muiden algebrallisia rakenteita koskevien ongelmien ratkaiseminen on kehittymässä uudeksi hyvin haastavaksi ja kiehtovaksi tietokonealgebran tutkimusalaksi.
Vuonna 1961 Erdös [2, s. 240] esitti kysymyksen, voidaanko Abelin neliöt välttää äärettömissä sanoissa, ts. onko Abelin neliöistä vapaiden sanojen määrä ääretön annetussa aakkostossa. Abelin neliö tarkoittaa ei-tyhjää äärellistä (mutta muutoin mielivaltaista) pituutta olevaa sanaa uv, missä u ja v ovat toistensa permutaatioita. Esimerkiksi abcacb on Abelin neliö. Sanaa kutsutaan Abelin neliöistä vapaaksi, jos sen osasanojen joukossa ei ole yhtään Abelin neliötä. Esimerkiksi sana abacaba on Abelin neliöistä vapaa, kun taas abcdadcada ei ole (se sisältää osasanan cda dca).
Vuonna 1970 Pleasants [6] osoitti, että viisikirjaimisessa aakkostossa voidaan määritellä Abelin neliöistä vapaita äärettömiä sanoja.
Nelikirjaimisen aakkoston tapaus oli pitkään avoin, kunnes vuonna 1991, ks. Keränen [3], onnistuimme todistamaan että em. endomorfismin g iterointi tuottaa "raja-arvonaan" Abelin neliöistä vapaan äärettömän sanan. Kaulakorun kuvassa tämän äärettömän (itseänsä lukevan) sanan alku, ts. g(abcacd ) = g(a) g(b) g(c) g(a) g(c) g(d), on esitetty 6*85 värillisen, kuudella kierroksella olevan, monitahokkaan avulla. Kierrokset alkavat alhaaltapäin ja jokainen niistä esittää ketjun alusta luettujen kirjainten kuvasanoja. Siten ensimmäinen kierros on g(a), toinen kierros on g(b), ja niiden jälkeen tulevat g(c), g(a), g(c) ja g(d).
Nelikirjaiminen aakkosto on erikoisasemassa siinä että se on pienin aakkosto, jonka äärettömissä sanoissa Abelin neliöt voidaan välttää. Todellakin, kolmen kirjaimen tapauksessa jokainen pituutta 8 oleva sana sisältää Abelin neliön. Voisiko tämä erikoisasema jotenkin liittyä luonnon käyttämään perimän koodiin? - Myös DNA rakentuu neljästä eri merkistä.
Osa tästä tiivistelmästä on julkaistu artikkelissa [4].