; TeX output 2002.02.13:1605 Kb&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MUVgcolor push Black color popZVg5PSfile=logo127.eps llx=0 lly=0 urx=99 ury=16 rwi=2880` wcolor push Black color popw"V
3
cmbx10IMPRtOVEDtBOUNDSONTHENUMBEROFTERNAR\YSQUARE-FREE WtORDS ɘcolor push Black color pop ɘo cmr9UWETGRIMM ,̍ color push Black -
cmcsc10Abstract. color popW=[Impro9ved-CuppAerandlo9wer-Cboundsonthen9umber-Cofsquare-freeternaryw9ordsare $ obtained.TheuppAerboundisbasedontheen9umerationofsquare-freeternarywordsuptolength$ 110.The{lo9werbAoundisderivedbyconstructinggeneralisedBrinkhuistriples.Theproblemof$ nding+suc9htriplescanessentiallybAereducedtoacombinatorialproblem,3whichcanecientlybAe$ treatedsb9ycomputer.Inparticular,itisshownthatthenumbAerofsquare-freeternarywordsofÍ$ lengthT5" cmmi9ngro9wsatleastas65-=; cmmi6n=Aa cmr640Hٺ,replacingthepreviousbAestlowerbAoundof2-=n=17Hٺ.chtml: html:
K`y
3
cmr101. ̩k -
3
cmcsc10Introduction ADw!ordD/"b>
3
cmmi10wisastringoflettersfromacertainalphabMet,WthenumbMeroflettersofwiscalledthelengthfofthew!ord.Thesetofwordsoflengthnis$!",
3
cmsy10L(n)
=#2 cmmi8nP,fandtheunionhtml: html:ы L
=&u
3
cmex10[
2Ln%K cmsy8!|{Y cmr80L(n)=z+pp msbm8Nq0g(1)is calledthelanguageofw!ordsinthealphabMet.aThisisamonoidwithconcatenationofwordsasopMerationandtheempt!yword,whichhaszerolength,asneutralelement[html:color push cmyk 0 1 0 012 color pop html:
4].ڻFeorawordwKn,w!ehdenoteby [wthecorrespMondingreversedword,hi.e.,thehwordobtainedbyreadingw-ֹfrombacktoffron!t.ApalindromeisawordwԹthatissymmetric,wV=H
w,. Square-free$w!ords[1{13]arewordsw\thatdonotcontaina\square"ydyuofawordyuasasubword(factor). n4In+otherw!ords,4wwFcanonlybMewrittenintheformxydyz{I,with+w!ordsx,ykandz{I,ify?=-Uistheempt!yword.Inatwo-letteralphabMetf0;11g,thecompletelistofsquare-freewordsisf;10;1;01;10;010;101g.Ho!wever, inathree-letteralphabMeto=f0;11;2g, square-freew!ordsofarbitrary)!lengthexist,B/andthen!umbMer)!ofsquare-freew!ordsofagivenlengthngrowsexpMonentiallywithfn[html:color push cmyk 0 1 0 04 color pop html:y,html:color push cmyk 0 1 0 03 color pop html: ,html:color push cmyk 0 1 0 07 color pop html:]. Wee'denotethesetofsquare-freew!ordsoflengthninthealphabMet
=f0;11;2g'byA(n)
L(n).Theflanguageofternarysquare-freew!ordsishtml: html:5Ѝ ^A
=[
2Ln0A(n)zNq0
q:g(2)Weefarein!terestedinthenumbMerofsquare-freewordsoflengthnhtml: html:` .Sa(n)
=jA(n)jg(3)and8inestimatingthegro!wthofa(n)withthelengthn.vRFeorn
=0;11;2;3,%the8setsofternary
square-freefw!ordsare SA(0)m=
fg;ύ SA(1)m=
f0;11;2g; SA(2)m=
f01;102;10;12;20;21g; SA(3)m=
f010;1012;020;021;101;102;120;121;201;202;210;212g; ghtml: html:(4) :9color push Black 1G color pop *Kb&6color push Blackhtml:color push gray 0 color pop html:2 ?UWEXGRIMMG color pop3ڍ&6हwhere.denotestheempt!yword. Hencea(0)
=1,a(1)=3,a(2)=6,a(3)=12,and.soon,see[html:color push cmyk 0 1 0 01 color pop html:y]
6wherefthevdDaluesofa(n)forn
90faretabulated.In[html:color push cmyk 0 1 0 016 color pop html:
4],thesequenceislistedasfhtml:color push cmyk 0 1 0 0A006156 color pop html:.6टMrhtml: html:
C4uf2. EUpper"boundsobtEainedbyenumeration Ob!viouslye,Ha19wordw|oflengthm+n,Hobtainedb!yconcatenationofwordswz1=oflengthmandwz2of@lengthn,UcanonlybMesquare-freeifwz1 ѹandwz2aresquare-free. Thisnecessarye,Ubutnotsucien!t,conditionfimpliestheinequalit!yhtml: html: =a(mn+n)
a(m)a(n)g(5)vforfallm;1n
0.Byfstandardargumen!ts,seealso[html:color push cmyk 0 1 0 01 color pop html:y],thisguaranteestheexistenceofthelimithtml: html:: s
:=,lim덓n!18a(n)5K133s^ \) 7n;g(6)thegro!wthrateor\connectiveconstant"ofternarysquare-freewords[html:color push cmyk 0 1 0 09 color pop html:y].2TheprecisevdDalueofsisTnotkno!wn,butlower[html:color push cmyk 0 1 0 04 color pop html:y,html:color push cmyk 0 1 0 03 color pop html: R,html:color push cmyk 0 1 0 07 color pop html:]anduppMerbounds[html:color push cmyk 0 1 0 01 color pop html:y]ha!veTbeenestablished.vItisthepurposeofthisfpapMertoimpro!vefboththelo!werfandtheupperbounds. Itisrelativ!elyeasytoderivereasonableuppMerboundsfromtheinequalit!y(html:color push cmyk 0 1 0 05 color pop html:).Infact[html:color push cmyk 0 1 0 01 color pop html:y],.onecan3sligh!tlyimproveon(html:color push cmyk 0 1 0 05 color pop html:)byconsideringtwowordswz17andwz2oflengthmG23andnG2,fsuc!hthatÄthelastt!woÄlettersofwz1areequaltotherstt!woÄlettersofwz2,andw!ejointhemtoawordwԹofflengthmn+n 2fb!yhavingthetwowordsoverlaponthesetwoletters.Thisyieldshtml: html:Ѝ Za(mn+n 2)
=ڹ1=ڟ㦉 p y
6
a(m)a(n);g(7)for0allm;1n2,S5bMecause0therearepreciselya(n)=6square-freelettersoflengthn20thatstartwithfthelastt!woflettersofwz1.Teakingnxed,oneobtainshtml: html:ܵ szn 2s=flim덑
m!1a(mn+n 2)ߟ㦉 p >
h5a(m)af=a(n)=ڟ㦉 p
6g(8)-andfhencetheuppMerboundhtml: html:I Դs
uMSa(n)MS㦉 p
6"au0r1+ʟs^ \) nq% cmsy6 2g(9)sforcolor push cmyk 0 1 0 01 color pop html:y],froma(90)
=2581615015792,fishtml: html: