%%Page: 1 1 1 0 bop Black 0 TeXcolorgray Black Black Black Black 10800 5267 a @beginspecial 0 @llx 0 @lly 99 @urx 16 @ury 2880 @rwi @setspecial%%BeginDocument: logo129.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: logo128.eps %%Creator: fig2dev Version 3.2.3 Patchlevel %%CreationDate: Thu Nov 8 16:13:04 2001 %%For: pope@fry.research.att.com (Sue Pope) %%BoundingBox: 0 0 99 16 %%Magnification: 0.1500 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 16 moveto 0 0 lineto 99 0 lineto 99 16 lineto closepath clip newpath -12.0 26.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin %%Page: 1 1 10 setmiterlimit 0.00900 0.00900 sc 7.500 slw % Ellipse n 2213 1988 856 856 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2213 1991 813 813 0 360 DrawEllipse gs col8 1.00 shd ef gr gs col8 s gr % Ellipse n 1602 1879 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2001 2575 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2831 1877 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2618 1509 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1806 1519 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2205 1364 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1669 2290 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2762 2305 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2439 2579 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2220 1992 440 440 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2618 1509 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1805 1515 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1669 2290 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2205 1360 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2762 2305 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1600 1875 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2439 2579 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2831 1877 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2001 2573 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr /Times-Bold ff 225.00 scf sf 1997 2652 m gs 1 -1 sc (23) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2438 2659 m gs 1 -1 sc (11) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Roman ff 480.00 scf sf 3375 2205 m gs 1 -1 sc (Article 03.4.2) col0 sh gr /Times-Roman ff 480.00 scf sf 3375 1650 m gs 1 -1 sc (Journal of Integer Sequences, Vol. 6 \(2003\),) col0 sh gr /Times-Bold ff 225.00 scf sf 2618 1592 m gs 1 -1 sc (2) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2830 1956 m gs 1 -1 sc (3) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2761 2386 m gs 1 -1 sc (6) dup sw pop 2 div neg 0 rm col0 sh gr % Ellipse n 1805 1517 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2554 1797 m 2554 1796 l 2554 1790 l 2554 1779 l 2554 1765 l 2553 1753 l 2552 1743 l 2550 1736 l 2548 1730 l 2544 1725 l 2540 1721 l 2534 1717 l 2528 1713 l 2521 1711 l 2514 1709 l 2507 1708 l 2499 1707 l 2492 1707 l 2483 1707 l 2474 1707 l 2465 1708 l 2456 1710 l 2447 1712 l 2438 1714 l 2431 1717 l 2423 1720 l 2416 1724 l 2408 1728 l 2401 1734 l 2394 1739 l 2388 1745 l 2382 1751 l 2377 1756 l 2372 1762 l 2368 1768 l 2363 1775 l 2359 1783 l 2356 1791 l 2352 1799 l 2350 1807 l 2348 1814 l 2346 1823 l 2345 1831 l 2345 1841 l 2345 1852 l 2346 1863 l 2349 1873 l 2352 1884 l 2356 1894 l 2360 1902 l 2365 1910 l 2371 1919 l 2378 1928 l 2385 1937 l 2393 1946 l 2401 1955 l 2409 1963 l 2417 1970 l 2425 1977 l 2435 1985 l 2446 1993 l 2457 2000 l 2467 2008 l 2477 2015 l 2487 2021 l 2494 2027 l 2501 2033 l 2506 2038 l 2510 2043 l 2513 2049 l 2515 2055 l 2516 2061 l 2516 2067 l 2516 2073 l 2514 2079 l 2510 2087 l 2505 2095 l 2498 2104 l 2490 2113 l 2481 2120 l 2473 2125 l 2465 2129 l 2458 2131 l 2449 2133 l 2440 2134 l 2431 2134 l 2422 2133 l 2414 2131 l 2406 2128 l 2396 2122 l 2385 2115 l 2375 2107 l 2366 2101 l 2359 2097 l 2353 2096 l 2350 2098 l 2347 2101 l 2346 2107 l 2344 2114 l 2344 2122 l 2344 2130 l 2345 2138 l 2346 2145 l 2347 2151 l 2349 2158 l 2352 2164 l 2355 2169 l 2360 2174 l 2364 2179 l 2370 2182 l 2375 2186 l 2382 2188 l 2390 2190 l 2399 2193 l 2409 2194 l 2419 2195 l 2429 2196 l 2438 2196 l 2448 2196 l 2456 2195 l 2465 2194 l 2475 2192 l 2484 2189 l 2493 2187 l 2501 2183 l 2509 2180 l 2516 2177 l 2524 2172 l 2533 2166 l 2541 2159 l 2548 2152 l 2555 2144 l 2560 2137 l 2565 2129 l 2569 2121 l 2573 2111 l 2576 2102 l 2579 2093 l 2581 2084 l 2583 2076 l 2584 2068 l 2584 2058 l 2584 2049 l 2583 2040 l 2582 2032 l 2580 2023 l 2577 2014 l 2572 2004 l 2568 1994 l 2563 1984 l 2558 1976 l 2552 1968 l 2546 1960 l 2538 1952 l 2531 1945 l 2524 1938 l 2517 1932 l 2509 1926 l 2501 1921 l 2493 1914 l 2484 1908 l 2476 1902 l 2468 1897 l 2461 1890 l 2453 1883 l 2445 1876 l 2437 1869 l 2431 1862 l 2427 1856 l 2423 1849 l 2420 1842 l 2418 1835 l 2417 1830 l 2417 1825 l 2417 1820 l 2417 1816 l 2418 1812 l 2419 1808 l 2419 1806 l 2420 1803 l 2421 1801 l 2422 1798 l 2424 1796 l 2425 1794 l 2427 1792 l 2429 1789 l 2431 1787 l 2433 1785 l 2436 1783 l 2437 1781 l 2439 1780 l 2442 1779 l 2444 1778 l 2446 1778 l 2448 1777 l 2450 1777 l 2452 1777 l 2455 1777 l 2457 1777 l 2460 1776 l 2462 1776 l 2465 1775 l 2468 1775 l 2470 1775 l 2473 1775 l 2476 1775 l 2479 1776 l 2482 1776 l 2484 1777 l 2487 1777 l 2489 1777 l 2492 1778 l 2495 1779 l 2498 1780 l 2502 1782 l 2506 1785 l 2510 1788 l 2514 1790 l 2517 1792 l 2520 1794 l 2522 1795 l 2524 1796 l 2525 1798 l 2527 1799 l 2529 1800 l 2531 1802 l 2534 1805 l 2536 1807 l 2539 1809 l 2540 1811 l 2542 1812 l 2544 1813 l 2546 1814 l 2547 1814 l 2549 1813 l 2550 1811 l 2552 1808 l 2554 1804 l 2555 1801 l 2556 1798 l 2556 1796 l 2557 1795 l 2557 1793 l 2557 1792 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1871 1753 m 1902 1705 l 2090 1705 l 2075 1753 l 2075 2255 l 2012 2317 l 1933 2317 l 2012 2255 l 2012 1753 l 1871 1753 l 1918 1737 l cp gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2169 1705 m 2278 1705 l 2263 1720 l 2247 1753 l 2247 2129 l 2278 2191 l 2152 2191 l 2169 2176 l 2185 2129 l 2185 2098 l 2185 1753 l cp gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1600 1877 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr /Times-Bold ff 225.00 scf sf 2197 1439 m gs 1 -1 sc (1) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 1667 2376 m gs 1 -1 sc (47) dup sw pop 2 div neg 0 rm col0 sh gr $F2psEnd rs %%EndDocument @endspecial Black Black 3071 11449 a Fs(On)861 b(a)f(class)h(of)g(Th) -72 b(ue-Morse)862 b(t)-72 b(yp)72 b(e)862 b(sequences)20476 16592 y Fr(Ricardo)520 b(Astudillo)p 0 .5 0 TeXcolorrgb -579 x Fq(1)p (#Hfootnote.1) [[365 568 370 580] [1 1 1 [3 3]] [0 0 1]] pdfm Black 17160 18584 a Fr(Departmen)-43 b(t)520 b(of)g(Mathematics)19877 20577 y(Univ)-43 b(ersit)g(y)517 b(of)k(Illinois)20807 22569 y(Urbana,)g(IL)f(61801)25196 24562 y(USA)p 0 1 0 0 TeXcolorcmyk 17777 26554 a Fp(rastudil@math.uiuc.edu)p [[232 478 394 490] [1 1 1 [3 3]] [0 0 1]] (mailto:rastudil@math.uiuc.edu) pdfm Black Black Black 24133 31087 a Fo(Abstract)p Black Black 5870 33323 a Fn(W)-101 b(e)432 b(consider)h(a)g(class)g(of)g(binary)g (sequences)g(that)h(generalize)e(the)h(Th)-34 b(ue-Morse)434 b(sequence.)4052 34828 y(In)527 b(particular,)558 b(w)-34 b(e)528 b(in)-34 b(v)g(estigate)528 b(the)g(o)34 b(ccurrences)526 b(of)i(palindromes)g(in)f(suc)-34 b(h)529 b(sequences.)908 b(W)-101 b(e)4052 36334 y(also)445 b(in)-34 b(tro)34 b(duce)446 b(the)h(notion)f(of)g(the)g(\257rst)h(di\256erence)d(of)i(a) g(binary)g(sequence)f(and)h(c)-34 b(haracterize)4052 37839 y(\257rst)584 b(di\256erences)f(of)h(our)f(class)h(of)f(Th)-34 b(ue-Morse)585 b(t)-34 b(yp)34 b(e)584 b(sequences.)1076 b(Finally)-101 b(,)628 b(w)-34 b(e)584 b(de\257ne)g(the)4052 39344 y(concept)413 b(of)g(a)f(\\c)-34 b(hange)414 b(sequence")e(of)h (a)f(giv)-34 b(en)413 b(binary)f(sequence,)i(a)f(sequence)f(whic)-34 b(h)414 b(enco)34 b(des)4052 40850 y(the)438 b(p)34 b(ositions)438 b(at)g(whic)-34 b(h)439 b(a)e(binary)h(sequence)f(c)-34 b(hanges)438 b(v)-67 b(alues.)639 b(W)-101 b(e)437 b(c)-34 b(haracterize)437 b(the)h(c)-34 b(hange)4052 42355 y(sequences)403 b(corresp)34 b(onding)405 b(to)f(our)g(class)g(of)h(Th)-34 b(ue-Morse)405 b(t)-34 b(yp)34 b(e)404 b(sequences.)800 46791 y Fm(1)2152 b(In)-60 b(tro)60 b(duction)800 49711 y Fl(The)434 b(Th)-36 b(ue-Morse)432 b(sequence)12590 52635 y Fk(f)p Fj(t)p Fl(\()p Fj(n)p Fl(\))p Fk(g)16176 52086 y Fi(1)16176 52963 y Fh(n)p Fg(=0)18374 52635 y Fl(=)369 b(0)p Fj(;)221 b Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g(:)g(:)g(:)800 55558 y Fl(is)480 b(de\257ned)e(b)-36 b(y)479 b Fj(t)p Fl(\()p Fj(n)p Fl(\))446 b(=)h(0)480 b(if)g Fj(n)f Fl(has)h(an)f(ev)-36 b(en)479 b(sum)g(of)h(binary)g (digits,)491 b(and)479 b Fj(t)p Fl(\()p Fj(n)p Fl(\))446 b(=)h(1)480 b(otherwise.)716 b(This)800 57163 y(sequence)429 b(has)f(attracted)g(m)-36 b(uc)g(h)428 b(atten)-36 b(tion)428 b(since)h(its)f(disco)-36 b(v)g(ery)430 b(b)-36 b(y)428 b(Axel)i(Th)-36 b(ue)428 b(in)g(the)h(early)g(1900's,)800 58768 y(and)580 b(is)g(still)g(the)g(fo)36 b(cus)580 b(of)h(m)-36 b(uc)g(h)579 b(study)-108 b(.)1017 b(The)580 b(Th)-36 b(ue-Morse)579 b(sequence)g(can)h(b)36 b(e)580 b(constructed)f(in)h(a)800 60373 y(surprising)378 b(v)-72 b(ariet)-36 b(y)380 b(of)f(w)-36 b(a)g(ys)380 b(and)e(has)h(n)-36 b(umerous)377 b(applications)j(in)e(div)-36 b(erse)379 b(\257elds)f(suc)-36 b(h)378 b(as)h(di\256eren)-36 b(tial)800 61978 y(geometry)-108 b(,)434 b(algebra,)h(n)-36 b(um)g(b)36 b(er)432 b(theory)-108 b(,)433 b(and)h(ph)-36 b(ysics;)433 b(see,)h(for)g(example,)h([)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.ubiquitous) [[417 159 423 171] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)2751 63583 y(The)609 b(Th)-36 b(ue-Morse)607 b(sequence)h(can)h(b)36 b(e)608 b(generalized)h(as)g(follo)-36 b(ws:)930 b(F)-108 b(or)608 b Fj(k)712 b Fk(\270)667 b Fl(2,)652 b(de\257ne)608 b Fj(s)48672 63782 y Fh(k)49240 63583 y Fl(\()p Fj(n)p Fl(\))h(as)800 65188 y(the)515 b(sum)h(of)g(digits)g(in)g(the)f(base-)p Fj(k)560 b Fl(represen)-36 b(tation)515 b(of)i(a)f(nonnegativ)-36 b(e)516 b(in)-36 b(teger)516 b Fj(n)p Fl(,)537 b(and)515 b(let)h Fj(t)48923 65387 y Fh(k)49491 65188 y Fl(\()p Fj(n)p Fl(\))509 b(=)p Black 800 66093 20800 45 v 2296 66909 a Ff(1)p 0 TeXcolorgray Black 2793 67311 a Fq(This)375 b(w)-31 b(ork)376 b(w)-31 b(as)376 b(done)f(while)i(the)e(author)h(w)-31 b(as)376 b(supp)31 b(orted)375 b(b)-31 b(y)375 b(an)h(NSF)e(REU)i(\(Researc)-31 b(h)375 b(Exp)31 b(erience)375 b(for)g(Under-)800 68639 y(graduates\))449 b(program)f(at)g(the)g(Univ)-31 b(ersit)g(y)449 b(of)f(Illinois)h(in)f(Summer)g(2001)h(and)f(Spring)f(2002,)470 b(and)447 b(b)-31 b(y)448 b(the)g(Ronald)g(E.)800 69967 y(McNair)380 b(Sc)-31 b(holars)380 b(Program)h(in)f(Summer)f(2002.)526 b(The)380 b(author)g(w)-31 b(ould)381 b(lik)-31 b(e)381 b(to)f(thank)h(the)f(referee)e(for)i(a)g(thorough)h(and)800 71296 y(helpful)370 b(rep)31 b(ort.)p Black Black 26475 74617 a Fl(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black Black 800 1424 a Fj(s)1413 1623 y Fh(k)1982 1424 y Fl(\()p Fj(n)p Fl(\))369 b(mo)36 b(d)369 b(2.)572 b(The)414 b(sequence)g Fk(f)p Fj(t)17743 1623 y Fh(k)18312 1424 y Fl(\()p Fj(n)p Fl(\))p Fk(g)20764 942 y Fi(1)20764 1752 y Fh(n)p Fg(=0)23006 1424 y Fl(is)h(th)-36 b(us)413 b(a)h(binary)g(sequence,)419 b(and)413 b(the)h(sp)36 b(ecial)414 b(case)h Fj(k)f Fl(=)369 b(2)800 3029 y(yields)434 b(the)f(Th)-36 b(ue-Morse)433 b(sequence)h Fj(t)19790 3228 y Fg(2)20315 3029 y Fl(\()p Fj(n)p Fl(\))369 b(=)g Fj(t)p Fl(\()p Fj(n)p Fl(\).)2751 4634 y(In)591 b(a)h(recen)-36 b(t)590 b(pap)36 b(er,)631 b(Allouc)-36 b(he)592 b(and)e(Shallit)i([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.palindromes) [[314 675 319 687] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])g(in)-36 b(v)g(estigated)592 b(palindromes)f(in)g(the)g (sequences)800 6239 y Fk(f)p Fj(t)1934 6438 y Fh(k)2503 6239 y Fl(\()p Fj(n)p Fl(\))p Fk(g)p Fl(.)644 b(Here)455 b(a)h(palindrome)f(is)h(de\257ned)e(in)h(the)g(usual)g(sense:)622 b(a)456 b(sequence)f(digits)h(is)g(a)f(palindrome)800 7844 y(if)474 b(it)f(reads)g(the)f(same)h(forw)-36 b(ard)474 b(and)e(bac)-36 b(kw)g(ard.)697 b(F)-108 b(or)472 b(example,)484 b(in)473 b(the)f(Th)-36 b(ue-Morse)473 b(sequence,)483 b(the)800 9450 y(\257rst)538 b(four)h(terms)g(0,1,1,0)i(form)e(a)g (palindrome,)566 b(as)539 b(do)g(the)f(\257rst)g(16)i(terms.)893 b(Allouc)-36 b(he)539 b(and)g(Shallit)800 11055 y(pro)-36 b(v)g(ed)433 b(the)g(follo)-36 b(wing)436 b(result:)p Black 800 13329 a Fe(Theorem)471 b(A)f(\(Allouc)-42 b(he)471 b(and)f(Shallit)h([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.palindromes) [[282 597 289 609] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\).)p Black 535 w Fd(F)-100 b(or)443 b(al)66 b(l)443 b Fj(k)414 b Fk(\270)369 b Fl(2)p Fd(,)446 b(the)c(se)-66 b(quenc)g(e)440 b Fk(f)p Fj(t)42826 13528 y Fh(k)43395 13329 y Fl(\()p Fj(n)p Fl(\))p Fk(g)45847 12846 y Fi(1)45847 13657 y Fh(n)p Fg(=0)48118 13329 y Fd(c)-66 b(ontains)800 14934 y(p)g(alindr)g(omes)464 b(of)g(arbitr)-66 b(ary)464 b(length.)2751 17207 y Fl(In)583 b(our)g(main)h(result,)621 b(Theorem)p 0 1 0 0 TeXcolorcmyk 583 w(5.1)p (#theorem.5.1) [[254 562 269 574] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)h(w)-36 b(e)584 b(generalize)g(this)f(result)g(to)h(a)g(larger) g(class)g(of)g(binary)800 18813 y(sequences)501 b(\(whic)-36 b(h)501 b(con)-36 b(tains)502 b(the)e(sequences)i Fk(f)p Fj(t)25649 19012 y Fh(k)26217 18813 y Fl(\()p Fj(n)p Fl(\))p Fk(g)p Fl(\).)782 b(These)502 b(sequences)f(also)h(can)g(b)36 b(e)501 b(de\257ned)f(as)800 20418 y(\257xed)433 b(p)36 b(oin)-36 b(ts)434 b(of)g(a)g(class)g(of)g(mappings)g(on)f(binary)h(w) -36 b(ords.)2751 22023 y(In)461 b(the)g(course)g(of)h(pro)-36 b(ving)462 b(this)f(result,)468 b(w)-36 b(e)462 b(in)-36 b(tro)36 b(duce)460 b(the)h(concept)g(of)h(the)f(\257rst)f (di\256erence)h(of)h(a)800 23628 y(binary)482 b(sequence.)722 b(In)482 b(Theorem)p 0 1 0 0 TeXcolorcmyk 481 w(4.1)p (#theorem.4.1) [[236 504 251 516] [1 1 1 [3 3]] [0 0 1]] pdfm Black 483 w(w)-36 b(e)482 b(c)-36 b(haracterize)482 b(the)f(\257rst)g (di\256erences)g(of)h(our)f(class)i(of)f(Th)-36 b(ue-)800 25233 y(Morse)311 b(t)-36 b(yp)36 b(e)311 b(sequences.)538 b(The)311 b(c)-36 b(haracterization)312 b(in)-36 b(v)g(olv)g(es)312 b(another)f(class)h(of)g(maps,)336 b(so-called)311 b(T)-108 b(o)36 b(eplitz)800 26838 y(maps,)434 b(whic)-36 b(h)433 b(w)-36 b(e)434 b(study)f(in)g(Section)p 0 1 0 0 TeXcolorcmyk 434 w(2)p (#section.2) [[251 475 257 487] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)2751 28443 y(W)-108 b(e)478 b(relate)h(the)f(\257rst)f (di\256erence)h(to)g(another)g(concept,)489 b(that)478 b(of)h(a)g(c)-36 b(hange)478 b(sequence)g(of)h(a)g(binary)800 30048 y(sequence.)936 b(This)553 b(is)g(a)g(sequence)g(whic)-36 b(h)552 b(enco)36 b(des)553 b(the)f(p)36 b(ositions)553 b(at)g(whic)-36 b(h)552 b(the)g(sequence)h(c)-36 b(hanges)800 31653 y(v)-72 b(alues.)674 b(In)465 b(a)h(recen)-36 b(t)464 b(pap)36 b(er,)473 b(Allouc)-36 b(he)466 b(et)f(al.)674 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.relative) [[300 432 306 444] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])465 b(determined)f(the)h(c)-36 b(hange)465 b(sequence)g(of)h(the)f(Th)-36 b(ue-)800 33258 y(Morse)434 b(sequence)f(and)g(pro)-36 b(v)g(ed)433 b(the)g(follo)-36 b(wing)436 b(result:)p Black 800 35532 a Fe(Theorem)359 b(B)f(\(Allouc)-42 b(he)361 b(et)d(al.)618 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.relative) [[245 397 252 409] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\).)p Black 460 w Fd(L)-66 b(et)352 b Fj(S)430 b Fd(b)-66 b(e)352 b(the)h(set)f(of)h(inte)-66 b(gers)351 b Fj(n)i Fd(such)h(that)e Fj(t)43779 35731 y Fg(2)44305 35532 y Fl(\()p Fj(n)46 b Fk(\241)g Fl(1\))369 b Fk(6)p Fl(=)g Fj(t)50088 35731 y Fg(2)50614 35532 y Fl(\()p Fj(n)p Fl(\))p Fd(,)800 37137 y(i.e.,)16413 38742 y Fj(S)446 b Fl(=)369 b Fk(f)p Fl(1)p Fj(;)221 b Fl(3)p Fj(;)g Fl(4)p Fj(;)g Fl(5)p Fj(;)g Fl(7)p Fj(;)g Fl(9)p Fj(;)g Fl(11)p Fj(;)g Fl(12)p Fj(;)g Fl(13)p Fj(;)g Fl(15)p Fj(;)g(:)g(:)g(:)13 b Fk(g)p Fj(:)800 40848 y Fd(Then)464 b Fj(S)543 b Fd(is)464 b(the)h(set)g(of)f(inte)-66 b(gers)463 b Fj(n)j Fd(such)f(that)g(an)g (even)e(p)-66 b(ower)465 b(of)g Fl(2)g Fd(exactly)g(divides)f Fj(n)p Fd(.)2751 43122 y Fl(In)433 b(Theorem)p 0 1 0 0 TeXcolorcmyk 434 w(3.1)p (#theorem.3.1) [[161 329 176 341] [1 1 1 [3 3]] [0 0 1]] pdfm Black 435 w(w)-36 b(e)433 b(generalize)i(this)e(result)g(to)h(our)f (class)i(of)f(Th)-36 b(ue-Morse)433 b(t)-36 b(yp)36 b(e)433 b(sequences.)800 47483 y Fm(2)2152 b(Notation)716 b(and)g (Preliminaries)800 50404 y Fl(W)-108 b(e)484 b(consider)g(the)f(set)h (\247)13516 49922 y Fi(\244)14526 50404 y Fl(of)g(\257nite)g(w)-36 b(ords)484 b(o)-36 b(v)g(er)484 b(the)f(alphab)36 b(et)484 b(\247)455 b(=)f Fk(f)p Fl(0)p Fj(;)221 b Fl(1)p Fk(g)p Fl(.)731 b(W)-108 b(e)484 b(also)h(consider)f(the)800 52009 y(set)444 b(\247)3780 51527 y Fi(1)5220 52009 y Fl(of)h(in\257nite)e(and)g(\257nite)g(w)-36 b(ords)444 b(o)-36 b(v)g(er)444 b(\247.)609 b(F)-108 b(or)444 b(a)g(\257nite)f(w) -36 b(ord)443 b Fj(w)480 b Fl(w)-36 b(e)444 b(let)g Fk(j)p Fj(w)36 b Fk(j)443 b Fl(denote)g(the)g(length)800 53614 y(of)387 b Fj(w)36 b Fl(,)396 b(and)386 b(w)-36 b(e)387 b(set)g Fk(j)p Fj(w)36 b Fk(j)368 b Fl(=)h Fk(1)387 b Fl(if)g Fj(w)422 b Fl(is)387 b(an)f(in\257nite)g(w)-36 b(ord.)563 b(W)-108 b(e)387 b(denote)f(the)g Fj(i)p Fl(th)f(letter)i (of)g Fj(w)422 b Fl(b)-36 b(y)387 b Fj(w)36 b Fl(\()p Fj(i)p Fl(\),)395 b(i.e.,)800 55219 y Fj(w)36 b Fl(\()p Fj(i)p Fl(\))391 b(=)h Fj(t)5487 55418 y Fh(i)6309 55219 y Fl(if)448 b Fj(w)427 b Fl(=)392 b Fj(t)10746 55418 y Fg(1)11272 55219 y Fj(t)11742 55418 y Fg(2)12488 55219 y Fj(:)221 b(:)g(:)i(t)14706 55418 y Fh(b)15164 55219 y Fl(,)451 b(where)c Fj(t)20217 55418 y Fh(k)21177 55219 y Fk(2)392 b Fl(\247)447 b(for)h(all)g Fj(k)45 b Fl(.)619 b(Giv)-36 b(en)447 b(t)-36 b(w)g(o)447 b(w)-36 b(ords)448 b Fj(w)40286 55418 y Fg(1)41258 55219 y Fl(and)f Fj(w)44731 55418 y Fg(2)45256 55219 y Fl(,)k(w)-36 b(e)448 b(let)f Fj(w)50819 55418 y Fg(1)51344 55219 y Fj(w)52274 55418 y Fg(2)800 56824 y Fl(denote)425 b(the)f(w)-36 b(ord)426 b(obtained)e(b)-36 b(y)426 b(the)e(concatenation)i(of)g Fj(w)30495 57023 y Fg(2)31445 56824 y Fl(to)g(the)f(righ)-36 b(t)424 b(of)i Fj(w)40796 57023 y Fg(1)41322 56824 y Fl(.)576 b(The)425 b(concatenation)800 58429 y(of)546 b(an)f(arbitrary)h(\257nite)e(or)i(in\257nite)e(sequence)i(of)g(w)-36 b(ords)545 b(is)h(denoted)e(analogously)-108 b(.)915 b(W)-108 b(e)545 b(de\257ne)g(the)800 60034 y Fd(c)-66 b(omplement)701 b Fl(of)578 b Fj(w)612 b Fl(to)577 b(b)36 b(e)576 b(the)h(w)-36 b(ord)576 b(obtained)h(b)-36 b(y)576 b(in)-36 b(terc)g(hanging)577 b(the)f(letters)g(0)i(and)e(1)h(in)g Fj(w)36 b Fl(,)612 b(or)800 61640 y(equiv)-72 b(alen)-36 b(tly)-108 b(,)439 b(b)-36 b(y)437 b(adding)g(1)g(mo)36 b(dulo)437 b(2)h(to)f(eac)-36 b(h)437 b(letter)g(of)g Fj(w)36 b Fl(.)588 b(W)-108 b(e)437 b(denote)g(the)f(complemen)-36 b(t)437 b(of)h Fj(w)472 b Fl(b)-36 b(y)p 800 62513 966 54 v 800 63245 a Fj(w)36 b Fl(.)2751 64850 y(W)-108 b(e)434 b(next)f(de\257ne)g(t)-36 b(w)g(o)433 b(morphisms,)h Fj(\301)21853 65049 y Fh(w)23040 64850 y Fl(and)g Fj(\303)26416 65049 y Fh(w)27169 64850 y Fl(,)g(on)g(\247)30710 64368 y Fi(1)31706 64850 y Fl(.)2751 66455 y(Let)f Fj(w)469 b Fl(b)36 b(e)434 b(a)f(w)-36 b(ord)434 b(with)g Fk(j)p Fj(w)36 b Fk(j)368 b(\270)h Fl(2.)579 b(W)-108 b(e)434 b(let)f Fj(\301)25465 66654 y Fh(w)26588 66455 y Fl(:)370 b(\247)28258 65973 y Fi(1)29623 66455 y Fk(!)g Fl(\247)32260 65973 y Fi(1)33690 66455 y Fl(b)36 b(e)433 b(the)g(morphism)g (de\257ned)f(b)-36 b(y)23669 68877 y Fj(\301)24439 69076 y Fh(w)25193 68877 y Fl(\(0\))369 b(=)g Fj(w)36 b(;)23669 70814 y(\301)24439 71013 y Fh(w)25193 70814 y Fl(\(1\))369 b(=)p 28605 70083 V 369 w Fj(w)35 b(:)p Black 26475 74617 a Fl(2)p Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fl(It)437 b(is)g(not)g(hard)f(to)h(see)g(that)f(if)h Fk(j)p Fj(w)36 b Fk(j)374 b(\270)h Fl(2)437 b(and)g Fj(w)36 b Fl(\(1\))373 b(=)i(0,)438 b(then)e(there)g(exists)h(a)h(unique)e (\257xed)g(p)36 b(oin)-36 b(t)800 3029 y(b)36 b(eginning)424 b(with)f(0)i(of)f(the)f(morphism)g Fj(\301)21317 3228 y Fh(w)22072 3029 y Fl(;)k(i.e.,)g(there)c(is)h(a)g(unique)g (in\257nite)f(w)-36 b(ord)423 b Fe(w)h Fl(b)36 b(eginning)424 b(with)800 4634 y(0)434 b(suc)-36 b(h)433 b(that)23397 6239 y Fe(w)370 b Fl(=)e Fj(\301)26996 6438 y Fh(w)27750 6239 y Fl(\()p Fe(w)q Fl(\))p Fj(:)800 8358 y Fl(F)-108 b(urthermore,)432 b Fe(w)i Fl(can)g(b)36 b(e)433 b(obtained)g(b)-36 b(y)434 b(iterating)f Fj(\301)27560 8557 y Fh(w)28315 8358 y Fl(:)19505 10810 y Fe(w)370 b Fl(=)e Fj(\301)23104 10262 y Fi(1)23104 11139 y Fh(w)24100 10810 y Fl(\(0\))h(:=)692 b(lim)27873 11607 y Fh(n)p Fi(!1)30547 10810 y Fj(\301)31317 10262 y Fh(n)31317 11139 y(w)32071 10810 y Fl(\(0\))p Fj(:)800 13620 y Fl(F)-108 b(or)440 b(example,)j(if)e Fj(w)416 b Fl(=)380 b(01,)443 b(then)c Fe(w)i Fl(is)g(the)e(Th)-36 b(ue-Morse)440 b(sequence)g(men)-36 b(tioned)440 b(in)g(the)g(in)-36 b(tro)36 b(duction.)800 15225 y(The)434 b(morphisms)f Fj(\301)10834 15424 y Fh(w)12021 15225 y Fl(are)h(sp)36 b(ecial)435 b(cases)f(of)g(so-called)g(symmetric)g(morphisms;)f(see)h ([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.frid) [[470 580 476 592] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)2751 16831 y(W)-108 b(e)434 b(also)g(consider)g(a)f (second)h(morphism)f Fj(\303)24870 17030 y Fh(w)25993 16831 y Fl(:)369 b(\247)27662 16349 y Fi(1)29028 16831 y Fk(!)g Fl(\247)31664 16349 y Fi(1)33094 16831 y Fl(de\257ned)432 b(b)-36 b(y)23273 19283 y Fj(\303)24119 19482 y Fh(w)24873 19283 y Fl(\()p Fj(a)p Fl(\))369 b(=)f Fj(w)36 b(a;)800 21735 y Fl(where)432 b Fj(a)369 b Fk(2)f Fl(\247.)579 b(Suc)-36 b(h)431 b(a)h(morphism)g(is)g(a)h(sp)36 b(ecial)433 b(case)g(of)g(the)e Fd(T)-100 b(o)-66 b(eplitz)464 b(morphisms)542 b Fl(\(see)432 b([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.toeplitz) [[492 521 497 533] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)p 0 1 0 0 TeXcolorcmyk 432 w(5)p (#cite.toeplitz2) [[505 521 510 533] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\).)578 b(It)433 b(is)800 23340 y(not)j(hard)g(to)h(see)g(that)f (there)g(is)h(a)g(unique)f(\257xed)g(p)36 b(oin)-36 b(t)436 b(of)i Fj(\303)31504 23539 y Fh(w)32694 23340 y Fl(b)36 b(eginning)437 b(with)f Fj(w)36 b Fl(\(1\);)438 b(i.e.,)h(there)d(is)h (a)800 24945 y(unique)c(in\257nite)g(w)-36 b(ord)434 b Fj(w)13581 25144 y Fi(\244)14540 24945 y Fl(with)f Fj(w)18432 25144 y Fi(\244)18958 24945 y Fl(\(1\))369 b(=)f Fj(w)36 b Fl(\(1\))433 b(suc)-36 b(h)433 b(that)22983 27398 y Fj(w)23913 27597 y Fi(\244)24808 27398 y Fl(=)368 b Fj(\303)27034 27597 y Fh(w)27788 27398 y Fl(\()p Fj(w)29224 27597 y Fi(\244)29750 27398 y Fl(\))p Fj(;)800 29850 y Fl(and)433 b(w)-36 b(e)434 b(can)g(obtain)f Fj(w)12605 30049 y Fi(\244)13564 29850 y Fl(b)-36 b(y)434 b(iterating)g Fj(\303)21492 30049 y Fh(w)22246 29850 y Fl(:)17240 32302 y Fj(w)18170 32501 y Fi(\244)19065 32302 y Fl(=)369 b Fj(\303)21340 31754 y Fi(1)21292 32631 y Fh(w)22335 32302 y Fl(\()p Fj(w)36 b Fl(\(1\)\))368 b(:=)692 b(lim)28085 33099 y Fh(n)p Fi(!1)30759 32302 y Fj(\303)31653 31754 y Fh(n)31605 32631 y(w)32359 32302 y Fl(\()p Fj(w)36 b Fl(\(1\)\))p Fj(:)800 35113 y Fl(The)434 b(\257xed)f(p)36 b(oin)-36 b(t)433 b Fj(w)10943 35312 y Fi(\244)11902 35113 y Fl(is)h(of)g(the)f(form)16701 37565 y Fj(w)17631 37764 y Fi(\244)18526 37565 y Fl(=)369 b Fj(w)469 b(w)22236 37764 y Fi(\244)22761 37565 y Fl(\(1\))434 b Fj(w)469 b(w)27186 37764 y Fi(\244)27711 37565 y Fl(\(2\))434 b Fj(w)469 b(w)32136 37764 y Fi(\244)32662 37565 y Fl(\(3\))221 b Fk(\242)g(\242)g(\242)443 b Fj(:)800 40017 y Fl(This)434 b(allo)-36 b(ws)435 b(one)f(to)f(construct)g Fj(w)18263 40216 y Fi(\244)19222 40017 y Fl(b)-36 b(y)434 b(starting)f(with)h(a)g (sequence)f(of)h(the)g(form)22515 42470 y Fj(w)p 23914 42682 434 54 v 1336 w(w)p 26180 42682 V 1337 w(w)p 28447 42682 V 1557 w Fk(\242)221 b(\242)g(\242)800 44922 y Fl(and)433 b(successiv)-36 b(ely)435 b(\257lling)f(in)f(the)g(\\holes") i(with)f(the)f(terms)g(of)h(this)f(sequence.)2751 46527 y(Allouc)-36 b(he)470 b(et)h(al.)688 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.relative) [[181 298 187 310] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)480 b(pp.)687 b(456{458])473 b(sho)-36 b(w)g(ed)470 b(that)g(if)h Fj(w)c Fl(=)431 b(101,)480 b(then)470 b Fj(w)39649 46726 y Fi(\244)40644 46527 y Fl(enco)36 b(des)471 b(the)e(places)i(at)800 48132 y(whic)-36 b(h)380 b(the)g(Th)-36 b(ue-Morse)380 b(sequence)g(c)-36 b(hanges)380 b(v)-72 b(alues,)392 b(i.e.,)h Fj(w)31468 48331 y Fi(\244)31993 48132 y Fl(\()p Fj(n)p Fl(\))369 b(=)g(1)381 b(if)g(and)f(only)h(if)g Fj(t)p Fl(\()p Fj(n)p Fl(\))369 b Fk(6)p Fl(=)f Fj(t)p Fl(\()p Fj(n)187 b Fk(\241)g Fl(1\).)2751 49737 y(In)391 b(Sections)p 0 1 0 0 TeXcolorcmyk 392 w(4)p (#section.4) [[156 269 162 281] [1 1 1 [3 3]] [0 0 1]] pdfm Black 392 w(and)p 0 1 0 0 TeXcolorcmyk 391 w(5)p (#section.5) [[188 269 194 281] [1 1 1 [3 3]] [0 0 1]] pdfm Black 392 w(w)-36 b(e)392 b(shall)g(need)f(an)g(op)36 b(eration)392 b Fk(\251)g Fl(on)f(the)g(set)h(\247)37649 49255 y Fi(\244)38567 49737 y Fl(that)f(is)h(de\257ned)e(as)i(follo)-36 b(ws:)800 51342 y(Let)433 b Fj(w)469 b Fl(and)433 b Fj(v)481 b Fl(b)36 b(e)434 b(binary)f(w)-36 b(ords)434 b(of)g(the)f(same)h (length)f Fj(b)p Fl(.)579 b(Then)9305 53795 y Fj(w)10235 53994 y Fg(1)11056 53795 y Fk(\251)295 b Fj(w)13314 53994 y Fg(2)14209 53795 y Fl(=)369 b(\()p Fj(w)17026 53994 y Fg(1)17551 53795 y Fl(\(1\))295 b(+)g Fj(w)21745 53994 y Fg(2)22270 53795 y Fl(\(1\)\)\()p Fj(w)25874 53994 y Fg(1)26400 53795 y Fl(\(2\))g(+)g Fj(w)30594 53994 y Fg(2)31119 53795 y Fl(\(2\)\))221 b Fk(\242)g(\242)g(\242)h Fl(\()p Fj(w)36715 53994 y Fg(1)37241 53795 y Fl(\()p Fj(b)p Fl(\))295 b(+)f Fj(w)41337 53994 y Fg(2)41863 53795 y Fl(\()p Fj(b)p Fl(\)\))p Fj(;)800 56247 y Fl(where)434 b(addition)f(is)h(tak)-36 b(en)434 b(mo)36 b(dulo)433 b(2.)2751 57852 y(T)-108 b(o)569 b(conclude)g(this)f(section,)603 b(w)-36 b(e)569 b(de\257ne)f(a)h(pro)36 b(duct)568 b(op)36 b(eration)569 b Fk(\243)g Fl(on)g(\247)40438 57370 y Fi(\244)41532 57852 y Fl(as)h(follo)-36 b(ws:)850 b(F)-108 b(or)569 b(an)-36 b(y)800 59457 y(w)g(ords)434 b Fj(w)36 b(;)221 b(v)416 b Fk(2)369 b Fl(\247)9316 58975 y Fi(\244)10276 59457 y Fl(with)433 b Fk(j)p Fj(v)48 b Fk(j)369 b Fl(=)f Fj(c)p Fl(,)434 b(set)19723 61910 y Fj(w)331 b Fk(\243)295 b Fl(0)370 b(=)e Fj(w)36 b(;)1522 b(w)331 b Fk(\243)295 b Fl(1)369 b(=)p 32550 61178 966 54 v 369 w Fj(w)36 b(;)16249 b Fl(\(2.1\))800 64362 y(and)14252 65967 y Fj(w)331 b Fk(\243)295 b Fj(v)417 b Fl(=)368 b(\()p Fj(w)331 b Fk(\243)295 b Fj(v)48 b Fl(\(1\)\)\()p Fj(w)330 b Fk(\243)295 b Fj(v)48 b Fl(\(2\)\))221 b Fk(\242)g(\242)g(\242)h Fl(\()p Fj(w)331 b Fk(\243)295 b Fj(v)48 b Fl(\()p Fj(c)p Fl(\)\))p Fj(:)10777 b Fl(\(2.2\))800 68086 y(This)368 b(op)36 b(eration)368 b(w)-36 b(as)368 b(in)-36 b(tro)36 b(duced)366 b(b)-36 b(y)368 b(Jacobs)g(in)f([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.jacobs) [[306 104 318 116] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])h(and)f(w)-36 b(as)369 b(generalized)f(b)-36 b(y)367 b(Hoit)h([)p 0 1 0 0 TeXcolorcmyk(9)p (#cite.hoit2) [[473 104 479 116] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)p 0 1 0 0 TeXcolorcmyk 368 w(10)p (#cite.hoit) [[486 104 497 116] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])g(to)g(w)-36 b(ords)800 69691 y(o)g(v)g(er)508 b(alphab)36 b(ets)508 b Fk(f)p Fl(0)p Fj(;)221 b Fl(1)p Fj(;)g(:)g(:)g(:)226 b(;)221 b(m)p Fk(g)p Fl(.)802 b(This)508 b(pro)36 b(duct)507 b(is)i(closely)g(related)f(to)g(the)g(morphisms)f Fj(\301)47491 69890 y Fh(w)48754 69691 y Fl(de\257ned)800 71296 y(ab)36 b(o)-36 b(v)g(e;)435 b(indeed,)e(it)g(is)h(clear)g(that)f Fj(w)331 b Fk(\243)295 b Fj(v)417 b Fl(=)369 b Fj(\301)23646 71495 y Fh(w)24400 71296 y Fl(\()p Fj(v)48 b Fl(\).)p Black 26475 74617 a(3)p Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(3)2152 b(Change)716 b(Sequences)800 4345 y Fl(Let)433 b Fj(C)529 b Fl(b)36 b(e)433 b(the)g(set)h(of)g(indices)f Fj(n)h Fl(suc)-36 b(h)433 b(that)g Fj(t)23814 4544 y Fg(2)24340 4345 y Fl(\()p Fj(n)295 b Fk(\241)g Fl(1\))370 b Fk(6)p Fl(=)e Fj(t)30621 4544 y Fg(2)31147 4345 y Fl(\()p Fj(n)p Fl(\),)434 b(where)11663 7215 y Fk(f)p Fj(t)12797 7414 y Fg(2)13323 7215 y Fl(\()p Fj(n)p Fl(\))p Fk(g)15775 6666 y Fi(1)15775 7543 y Fh(n)p Fg(=0)17973 7215 y Fl(=)368 b Fk(f)p Fl(0)p Fj(;)221 b Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g Fl(1)p Fj(;)g Fl(1)p Fj(;)g Fl(0)p Fj(;)g(:)g(:)g(:)19 b Fk(g)800 10085 y Fl(is)508 b(the)f(Th)-36 b(ue-Morse)507 b(sequence.)800 b(As)508 b(stated)f(in)g(the)g(In)-36 b(tro)36 b(duction)507 b(\(see)g(Theorem)h (B\),)g(the)f(set)g Fj(C)603 b Fl(is)800 11690 y(c)-36 b(haracterized)471 b(b)-36 b(y)471 b(the)g(prop)36 b(ert)-36 b(y)471 b(that)g Fj(n)433 b Fk(2)g Fj(C)566 b Fl(if)472 b(and)f(only)h(if)g(an)f(ev)-36 b(en)471 b(p)36 b(o)-36 b(w)g(er)471 b(of)h(2)g(exactly)h(divides)800 13295 y Fj(n)p Fl(.)676 b(In)465 b(this)h(section)g(w)-36 b(e)466 b(generalize)h(this)f(result)f(to)h(the)f(class)i(of)g(all)g(\257xed)e (p)36 b(oin)-36 b(ts)466 b(of)g(the)g(morphisms)800 14900 y Fj(\301)1570 15099 y Fh(w)2324 14900 y Fl(.)579 b(T)-108 b(o)433 b(this)h(end,)f(w)-36 b(e)434 b(in)-36 b(tro)36 b(duce)432 b(the)h(concept)h(of)g(a)g(c)-36 b(hange)433 b(sequence)h(of)g(a)g(w)-36 b(ord)433 b(as)h(follo)-36 b(ws:)p Black 800 17558 a Fe(De\257nition)666 b(3.1.)p Black 627 w Fl(Let)578 b Fj(w)613 b Fl(b)36 b(e)578 b(a)g(\257nite)g (or)g(in\257nite)f(w)-36 b(ord)578 b(with)g Fk(j)p Fj(w)36 b Fk(j)614 b(\270)h Fl(2.)1012 b(W)-108 b(e)578 b(de\257ne)f(the)g(c) -36 b(hange)800 19163 y(sequence)434 b Fj(C)7122 19362 y Fh(w)8309 19163 y Fl(of)g Fj(w)469 b Fl(as)434 b(the)f(sequence)h(of) g Fj(n)370 b Fk(2)e(f)p Fl(1)p Fj(;)221 b Fl(2)p Fj(;)g(:)g(:)g(:)k(;)c Fk(j)p Fj(w)36 b Fk(j)296 b(\241)f Fl(1)p Fk(g)434 b Fl(suc)-36 b(h)433 b(that)g Fj(w)36 b Fl(\()p Fj(n)p Fl(\))369 b Fk(6)p Fl(=)f Fj(w)36 b Fl(\()p Fj(n)295 b Fl(+)g(1\).)2751 21821 y(F)-108 b(or)433 b(example,)i(if)f Fj(w)404 b Fl(=)369 b(0010)435 b(and)e Fe(w)h Fl(is)g(the)f(asso)36 b(ciated)434 b(in\257nite)f(w)-36 b(ord,)434 b(i.e.,)18895 24691 y Fe(w)370 b Fl(=)e(0010001011010010)221 b Fk(\242)g(\242)g(\242) 449 b Fj(;)800 27561 y Fl(then)433 b Fj(C)4694 27760 y Fh(w)5817 27561 y Fl(=)368 b Fk(f)p Fl(2)p Fj(;)221 b Fl(3)p Fk(g)435 b Fl(and)f Fj(C)14303 27760 y Fc(w)15510 27561 y Fl(=)369 b Fk(f)p Fl(2)p Fj(;)221 b Fl(3)p Fj(;)g Fl(6)p Fj(;)g Fl(7)p Fj(;)g Fl(8)p Fj(;)g Fl(10)p Fj(;)g Fl(11)p Fj(;)g Fl(12)p Fj(;)g(:)g(:)g(:)10 b Fk(g)p Fl(.)2751 29166 y(In)465 b(the)g(follo)-36 b(wing)467 b(theorem)e(w)-36 b(e)466 b(giv)-36 b(e)466 b(a)g(general)g(metho)36 b(d)464 b(for)i(determining)f Fj(C)42545 29365 y Fc(w)43849 29166 y Fl(for)h(an)f(arbitrary)800 30771 y(\257xed)433 b(p)36 b(oin)-36 b(ts)434 b Fe(w)p Fl(.)p Black 800 33429 a Fe(Theorem)427 b(3.1.)p Black 505 w Fd(L)-66 b(et)406 b Fj(w)443 b Fd(b)-66 b(e)406 b(a)h(wor)-66 b(d)407 b(with)g Fk(j)p Fj(w)36 b Fk(j)368 b Fl(=)h Fj(b)g Fk(\270)g Fl(2)407 b Fd(such)h(that)e Fj(w)36 b Fl(\(1\))369 b(=)f Fj(w)36 b Fl(\()p Fj(b)p Fl(\))368 b(=)h(0)p Fd(,)418 b(let)407 b Fe(w)390 b Fl(=)369 b Fj(\301)49744 32947 y Fi(1)49744 33757 y Fh(w)50740 33429 y Fl(\(0\))p Fd(,)800 35034 y(and)494 b(let)f Fj(C)6139 35233 y Fh(w)7387 35034 y Fd(b)-66 b(e)493 b(the)h(change)f(se)-66 b(quenc)g(e)492 b(of)i Fj(w)36 b Fd(.)684 b(Then)493 b Fj(C)28806 35233 y Fc(w)30082 35034 y Fl(=)423 b Fk(f)p Fj(n)g Fk(2)f Fb(N)h Fl(:)g Fj(d)37530 35233 y Fh(b)37988 35034 y Fl(\()p Fj(n)p Fl(\))g Fk(2)f Fj(C)42438 35233 y Fh(w)43192 35034 y Fk(g)p Fd(,)501 b(wher)-66 b(e)494 b Fj(d)49131 35233 y Fh(b)49588 35034 y Fl(\()p Fj(n)p Fl(\))g Fd(is)800 36639 y(the)465 b(last)g(non-zer)-66 b(o)464 b(digit)g(in)g(the)g(b)-66 b(ase-)p Fj(b)465 b Fd(r)-66 b(epr)g(esentation)462 b(of)j Fj(n)p Fd(.)p Black 800 39297 a(Pr)-66 b(o)g(of.)p Black 649 w Fl(Let)633 b Fj(w)745 b Fl(=)710 b Fj(t)11269 39496 y Fg(1)11794 39297 y Fj(t)12264 39496 y Fg(2)13011 39297 y Fk(\242)221 b(\242)g(\242)h Fj(t)15252 39496 y Fh(b)15710 39297 y Fl(.)1178 b(Since)634 b(for)g(1)710 b Fk(\267)g Fj(r)745 b Fk(\267)710 b Fj(b)432 b Fk(\241)f Fl(1)634 b(w)-36 b(e)634 b(ha)-36 b(v)g(e)634 b Fj(d)38933 39496 y Fh(b)39391 39297 y Fl(\()p Fj(n)p Fl(\))709 b(=)h Fj(r)669 b Fl(if)635 b(and)e(only)h(if)800 40902 y Fj(n)369 b Fl(=)g Fj(b)3879 40420 y Fh(i)4255 40902 y Fl(\()p Fj(bk)340 b Fl(+)295 b Fj(r)36 b Fl(\))433 b(for)h(some)g Fj(i;)221 b(k)415 b Fk(\270)369 b Fl(0,)434 b(it)g(su\261ces)f(to)h(sho)-36 b(w)433 b(that)15935 43772 y Fj(C)16866 43971 y Fc(w)18074 43772 y Fl(=)368 b Fk(f)p Fj(b)20671 43224 y Fh(i)21047 43772 y Fl(\()p Fj(bk)340 b Fl(+)295 b Fj(r)36 b Fl(\))369 b(:)g Fj(i;)221 b(k)415 b Fk(\270)369 b Fl(0)p Fj(;)1523 b(r)405 b Fk(2)368 b Fj(C)35885 43971 y Fh(w)36639 43772 y Fk(g)p Fj(:)12462 b Fl(\(3.1\))800 46642 y(T)-108 b(o)434 b(pro)-36 b(v)g(e)433 b(this,)h(it)g(su\261ces)f(to)h(sho)-36 b(w)433 b(the)g(follo)-36 b(wing)436 b(t)-36 b(w)g(o)434 b(equiv)-72 b(alences:)11957 49512 y Fj(r)405 b Fk(2)368 b Fj(C)15133 49711 y Fh(w)16625 49512 y Fk(\()-221 b(\))739 b Fj(bk)340 b Fl(+)295 b Fj(r)405 b Fk(2)369 b Fj(C)25852 49711 y Fc(w)29291 49512 y Fl(\()p Fj(k)414 b Fk(\270)369 b Fl(0,)434 b(1)370 b Fk(\267)f Fj(r)405 b Fk(\267)369 b Fj(b)296 b Fk(\241)f Fl(1\))p Fj(:)7883 b Fl(\(3.2\))11357 51450 y Fj(m)368 b Fk(2)h Fj(C)15049 51649 y Fc(w)16625 51450 y Fk(\()-221 b(\))739 b Fj(bm)368 b Fk(2)h Fj(C)24044 51649 y Fc(w)27484 51450 y Fl(\()p Fj(m)f Fk(\270)h Fl(1\))p Fj(:)17711 b Fl(\(3.3\))2751 54320 y(T)-108 b(o)523 b(pro)-36 b(v)g(e)522 b(\()p 0 1 0 0 TeXcolorcmyk(3.2)p (#equation.3.2) [[152 228 167 240] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q(,)544 b(notice)523 b(that)f Fe(w)e Fl(=)g Fj(w)22814 54519 y Fg(0)23339 54320 y Fj(w)24269 54519 y Fg(1)24795 54320 y Fj(w)25725 54519 y Fg(2)26250 54320 y Fj(w)27180 54519 y Fg(3)27927 54320 y Fj(:)221 b(:)g(:)524 b Fl(with)f Fj(w)33958 54519 y Fh(k)35046 54320 y Fk(2)d(f)p Fj(w)36 b(;)p 38664 53588 966 54 v 221 w(w)g Fk(g)522 b Fl(for)h(all)g Fj(k)45 b Fl(.)845 b(Clearly)524 b(w)-36 b(e)800 55925 y(ha)g(v)g(e)444 b Fj(C)4740 56124 y Fh(w)5882 55925 y Fl(=)386 b Fj(C)8211 56124 y Fh(w)8886 56280 y Fa(k)9894 55925 y Fl(for)445 b(all)g Fj(k)45 b Fl(.)610 b(Since)444 b(the)g(w)-36 b(ords)444 b Fj(w)25728 56124 y Fh(k)26741 55925 y Fl(all)h(ha)-36 b(v)g(e)445 b(length)f Fj(b)p Fl(,)j(for)e(1)387 b Fk(\267)g Fj(r)424 b Fk(\267)387 b Fj(b)444 b Fl(the)g(\()p Fj(bk)347 b Fl(+)303 b Fj(r)36 b Fl(\)th)800 57530 y(letter)524 b(in)g Fe(w)h Fl(is)g(equal)g(to)f (the)g Fj(r)36 b Fl(th)524 b(letter)g(in)h Fj(w)24977 57729 y Fh(k)25545 57530 y Fl(.)851 b(Hence,)547 b(for)525 b(1)f Fk(\267)f Fj(r)560 b Fk(\267)524 b Fj(b)357 b Fk(\241)g Fl(1)525 b(and)f(all)h Fj(k)45 b Fl(,)547 b(w)-36 b(e)525 b(ha)-36 b(v)g(e)800 59135 y Fe(w)p Fl(\()p Fj(bk)351 b Fl(+)305 b Fj(r)36 b Fl(\))395 b Fk(6)p Fl(=)g Fe(w)p Fl(\()p Fj(bk)351 b Fl(+)305 b Fj(r)342 b Fl(+)305 b(1\))449 b(if)h(and)e(only)h(if)h Fj(w)25303 59334 y Fh(k)25872 59135 y Fl(\()p Fj(r)36 b Fl(\))395 b Fk(6)p Fl(=)f Fj(w)30237 59334 y Fh(k)30806 59135 y Fl(\()p Fj(r)342 b Fl(+)305 b(1\);)457 b(i.e.,)d Fj(bk)350 b Fl(+)306 b Fj(r)431 b Fk(2)395 b Fj(C)44133 59334 y Fc(w)45420 59135 y Fl(if)449 b(and)g(only)g(if)800 60740 y Fj(r)405 b Fk(2)369 b Fj(C)3977 60939 y Fh(w)4652 61095 y Fa(k)5584 60740 y Fl(=)g Fj(C)7896 60939 y Fh(w)8650 60740 y Fl(.)578 b(This)434 b(pro)-36 b(v)g(es)433 b(\()p 0 1 0 0 TeXcolorcmyk(3.2)p (#equation.3.2) [[226 170 241 182] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q(.)2751 62345 y(T)-108 b(o)434 b(sho)-36 b(w)434 b(that)f(\()p 0 1 0 0 TeXcolorcmyk(3.3)p (#equation.3.3) [[173 156 188 168] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))h(holds,)g(\257x)f Fj(m)369 b Fk(\270)g Fl(1)434 b(and)f(c)-36 b(ho)36 b(ose)434 b Fj(j)444 b Fk(\270)369 b Fl(1)434 b(suc)-36 b(h)433 b(that)g(1)369 b Fk(\267)g Fj(m)g Fk(\267)g Fj(b)45172 61863 y Fh(j)45659 62345 y Fl(.)578 b(W)-108 b(e)434 b(set)20274 65215 y Fj(v)417 b Fl(=)368 b Fj(\301)23470 64667 y Fh(j)23470 65544 y(w)24224 65215 y Fl(\()p Fj(t)25200 65414 y Fg(1)25726 65215 y Fl(\))h(=)f Fj(t)28451 65414 y Fg(1)28977 65215 y Fj(t)29447 65414 y Fg(2)30194 65215 y Fk(\242)221 b(\242)g(\242)h Fj(t)32435 65450 y Fh(b)32838 65198 y Fa(j)800 68086 y Fl(and)381 b(note)f(that)h Fj(m)369 b Fk(2)f Fj(C)12572 68285 y Fc(w)13792 68086 y Fl(if)381 b(and)g(only)g(if)h Fj(m)369 b Fk(2)f Fj(C)25041 68285 y Fh(v)25586 68086 y Fl(.)561 b(By)382 b(de\257nition,)391 b Fj(m)368 b Fk(2)h Fj(C)38289 68285 y Fh(v)39215 68086 y Fl(if)381 b(and)g(only)h(if)f Fj(t)47242 68285 y Fh(m)48499 68086 y Fk(6)p Fl(=)368 b Fj(t)50349 68285 y Fh(m)p Fg(+1)52439 68086 y Fl(,)800 69691 y(whic)-36 b(h)433 b(is)h(equiv)-72 b(alen)-36 b(t)434 b(to)21250 71296 y Fj(\301)22020 71495 y Fh(w)22775 71296 y Fl(\()p Fj(t)23751 71495 y Fh(m)24638 71296 y Fl(\))368 b(=)p 26893 70140 5096 54 v 369 w Fj(\301)27663 71495 y Fh(w)28417 71296 y Fl(\()p Fj(t)29393 71495 y Fh(m)p Fg(+1)31483 71296 y Fl(\))o Fj(:)p Black 26475 74617 a Fl(4)p Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(No)-36 b(w)434 b(consider)12353 4358 y Fj(\301)13123 4557 y Fh(w)13877 4358 y Fl(\()p Fj(v)48 b Fl(\))368 b(=)g Fj(\301)18084 3809 y Fh(j)51 b Fg(+1)18084 4686 y Fh(w)19773 4358 y Fl(\()p Fj(t)20749 4557 y Fg(1)21275 4358 y Fl(\))15934 6295 y(=)368 b Fj(\301)18084 6494 y Fh(w)18839 6295 y Fl(\()p Fj(t)19815 6494 y Fg(1)20340 6295 y Fl(\))p Fj(\301)21616 6494 y Fh(w)22370 6295 y Fl(\()p Fj(t)23346 6494 y Fg(2)23871 6295 y Fl(\))221 b Fk(\242)g(\242)g(\242)i Fj(\301)27140 6494 y Fh(w)27894 6295 y Fl(\()p Fj(t)28870 6494 y Fh(m)29757 6295 y Fl(\))p Fj(\301)31033 6494 y Fh(w)31787 6295 y Fl(\()p Fj(t)32763 6494 y Fh(m)p Fg(+1)34852 6295 y Fl(\))e Fk(\242)g(\242)g(\242)i Fj(\301)38121 6494 y Fh(w)38875 6295 y Fl(\()p Fj(t)39851 6529 y Fh(b)40254 6277 y Fa(j)40742 6295 y Fl(\))15934 8481 y(=)368 b Fj(\301)18084 8680 y Fh(w)18839 8481 y Fl(\()p Fj(t)19815 8680 y Fg(1)20340 8481 y Fl(\))p Fj(\301)21616 8680 y Fh(w)22370 8481 y Fl(\()p Fj(t)23346 8680 y Fg(2)23871 8481 y Fl(\))221 b Fk(\242)g(\242)g(\242)i Fj(\301)27140 8680 y Fh(w)27894 8481 y Fl(\()p Fj(t)28870 8680 y Fh(m)29757 8481 y Fl(\))p 30263 7325 3894 54 v Fj(\301)31033 8680 y Fh(w)31787 8481 y Fl(\()p Fj(t)32763 8680 y Fh(m)33650 8481 y Fl(\))e Fk(\242)g(\242)g(\242)h Fj(\301)36918 8680 y Fh(w)37672 8481 y Fl(\()p Fj(t)38648 8716 y Fh(b)39051 8463 y Fa(j)39539 8481 y Fl(\))p Fj(:)800 11414 y Fl(Since)457 b Fk(j)p Fj(\301)5359 11613 y Fh(w)6113 11414 y Fl(\()p Fj(t)7089 11613 y Fh(i)7464 11414 y Fl(\))p Fk(j)408 b Fl(=)h Fj(b)457 b Fl(for)g(all)h Fj(i)e Fl(and)h Fj(\301)19241 11613 y Fh(w)19995 11414 y Fl(\()p Fj(t)20971 11613 y Fh(m)21858 11414 y Fl(\))g(b)36 b(egins)457 b(and)f(ends)g(with)h(the)g(same)g (letter,)463 b(it)457 b(follo)-36 b(ws)458 b(that)800 13020 y Fj(m)369 b Fk(2)f Fj(C)4492 13219 y Fc(w)5764 13020 y Fl(is)434 b(equiv)-72 b(alen)-36 b(t)434 b(to)g Fj(bm)369 b Fk(2)f Fj(C)19085 13226 y Fh(\301)19644 13337 y Fa(w)20311 13226 y Fg(\()p Fh(v)32 b Fg(\))21957 13020 y Fk(\275)369 b Fj(C)24290 13219 y Fc(w)25128 13020 y Fl(.)p 51860 13020 45 878 v 51905 12186 781 45 v 51905 13020 V 52684 13020 45 878 v Black 800 15732 a Fe(Remark.)p Black 606 w Fl(Theorem)p 0 1 0 0 TeXcolorcmyk 534 w(3.1)p (#theorem.3.1) [[185 575 200 587] [1 1 1 [3 3]] [0 0 1]] pdfm Black 536 w(requires)535 b(that)f Fj(w)570 b Fl(b)36 b(egins)535 b(and)f(ends)g(with)h(a)g(0.)882 b(Ho)-36 b(w)g(ev)g(er,)561 b(it)535 b(is)g(easy)h(to)800 17337 y(c)-36 b(hec)g(k)384 b(that)f(for)h(an)-36 b(y)384 b(w)-36 b(ord)384 b Fj(w)419 b Fl(with)384 b Fj(w)36 b Fl(\(1\))368 b(=)h(0,)394 b(the)383 b(w)-36 b(ord)384 b Fj(v)417 b Fl(=)368 b Fj(\301)33129 17536 y Fh(w)33883 17337 y Fl(\()p Fj(w)36 b Fl(\))368 b(=)h Fj(\301)38380 17536 y Fh(w)39134 17337 y Fl(\()p Fj(\301)40410 17536 y Fh(w)41164 17337 y Fl(\(0\)\))384 b(b)36 b(oth)383 b(b)36 b(egins)384 b(and)800 18942 y(ends)442 b(with)g(a)g(0.)605 b(Th)-36 b(us)442 b(w)-36 b(e)442 b(can)g(\257nd)f(the)h(c)-36 b(hange)442 b(sequence)g(of)h Fe(w)g Fl(b)-36 b(y)442 b(applying)h(Theorem)p 0 1 0 0 TeXcolorcmyk 442 w(3.1)p (#theorem.3.1) [[498 547 513 559] [1 1 1 [3 3]] [0 0 1]] pdfm Black 443 w(to)g(the)800 20547 y(w)-36 b(ord)434 b Fj(v)481 b Fl(and)433 b(noting)g(that)g Fe(v)369 b Fl(=)g(lim)18864 20746 y Fh(n)p Fi(!1)21594 20547 y Fj(\301)22364 20065 y Fh(n)22364 20875 y(v)22990 20547 y Fl(\(0\))g(=)f(lim)28208 20746 y Fh(n)p Fi(!1)30937 20547 y Fj(\301)31707 20065 y Fh(n)31707 20875 y(w)32461 20547 y Fl(\(0\))h(=)g Fe(w)p Fl(.)2751 23259 y(By)554 b(the)f(result)g(of)h(Allouc)-36 b(he)554 b(et)f(al.)939 b(quoted)553 b(in)h(the)f(In)-36 b(tro)36 b(duction)552 b(\(Theorem)i(B\),)f(the)g(c)-36 b(hange)800 24864 y(sequence)434 b(of)g Fe(01)g Fl(is)g(giv)-36 b(en)434 b(b)-36 b(y)16690 27797 y Fj(C)17621 27996 y Fc(01)19129 27797 y Fl(=)369 b Fk(f)p Fj(n)h Fl(=)e(2)24350 27249 y Fg(2)p Fh(i)25197 27797 y Fj(m)g Fl(:)i Fj(i)e Fk(\270)h Fl(0)p Fj(;)1523 b(m)433 b Fl(o)36 b(dd)p Fk(g)p Fj(:)13216 b Fl(\(3.4\))800 30731 y(W)-108 b(e)397 b(no)-36 b(w)397 b(v)-36 b(erify)398 b(this)e(with)h(Theorem)p 0 1 0 0 TeXcolorcmyk 397 w(3.1)p (#theorem.3.1) [[253 440 268 452] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)567 b(Since)396 b Fj(w)404 b Fl(=)369 b(01)397 b(ends)f(in)h(a)g(1,)405 b(w)-36 b(e)396 b(m)-36 b(ust)396 b(apply)h(the)f(theorem)800 32336 y(to)458 b Fj(v)h Fl(=)410 b Fj(\301)5694 32535 y Fg(01)6690 32336 y Fl(\(01\))i(=)e(0110.)654 b(W)-108 b(e)458 b(ha)-36 b(v)g(e)458 b Fk(j)p Fj(v)48 b Fk(j)411 b Fl(=)f(4)459 b(and)e Fj(C)27579 32535 y Fh(v)28535 32336 y Fl(=)411 b Fk(f)p Fl(1)p Fj(;)221 b Fl(3)p Fk(g)p Fl(,)466 b(and)458 b(so)g(b)-36 b(y)458 b(Theorem)p 0 1 0 0 TeXcolorcmyk 459 w(3.1)p (#theorem.3.1) [[482 426 497 438] [1 1 1 [3 3]] [0 0 1]] pdfm Black 459 w(it)g(follo)-36 b(ws)800 33941 y(that)13842 36874 y Fj(C)14773 37073 y Fc(01)16281 36874 y Fl(=)369 b Fk(f)p Fj(n)g Fl(=)g(4)21502 36326 y Fh(i)21878 36874 y Fl(\(4)p Fj(k)340 b Fl(+)295 b Fj(r)36 b Fl(\))369 b(:)h Fj(i;)221 b(k)414 b Fk(\270)369 b Fl(0)p Fj(;)1523 b(r)405 b Fk(2)369 b(f)p Fl(1)p Fj(;)221 b Fl(3)p Fk(gg)16281 38933 y Fl(=)369 b Fk(f)p Fj(n)g Fl(=)g(4)21502 38384 y Fh(i)21878 38933 y Fj(m)g Fl(:)g Fj(i)g Fk(\270)g Fl(0)p Fj(;)1523 b(m)433 b Fl(o)36 b(dd)o Fk(g)16281 40991 y Fl(=)369 b Fk(f)p Fj(n)g Fl(=)g(2)21502 40442 y Fg(2)p Fh(i)22349 40991 y Fj(m)f Fl(:)h Fj(i)g Fk(\270)g Fl(0)p Fj(;)1523 b(m)433 b Fl(o)36 b(dd)p Fk(g)p Fj(;)800 43924 y Fl(whic)-36 b(h)433 b(pro)-36 b(v)g(es)434 b(\()p 0 1 0 0 TeXcolorcmyk(3.4)p (#equation.3.4) [[153 322 168 334] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q(.)800 48361 y Fm(4)2152 b(First)716 b(Di\256erences)800 51282 y Fl(In)579 b(this)h(section)g(w)-36 b(e)579 b(de\257ne)g(the)g (concept)g(of)h(the)g(\257rst)e(di\256erence)h(of)i(a)e(w)-36 b(ord,)617 b(and)579 b(w)-36 b(e)580 b(determine)800 52887 y(the)476 b(\257rst)g(di\256erences)g(of)h(w)-36 b(ords)476 b Fj(\301)18245 52405 y Fi(1)18245 53215 y Fh(w)19241 52887 y Fl(\(0\))h(for)g Fj(w)36 b Fl(\(1\))441 b(=)h(0.)707 b(First)477 b(Di\256erences)f(of)h(w)-36 b(ords)477 b(o)-36 b(v)g(er)477 b(a)g(general)800 54492 y(alphab)36 b(et)578 b(ha)-36 b(v)g(e)578 b(b)36 b(een)577 b(used)g(implicitly)i(in)f(a)g(recen)-36 b(t)577 b(pap)36 b(er)578 b(of)g(F)-108 b(rid)577 b([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.frid) [[408 227 414 239] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)614 b(pp.)1011 b(359{360].)i(F)-108 b(or)578 b(\257rst)800 56097 y(di\256erences)433 b(of)h(in\257nite)f(in)-36 b(teger)433 b(sequences)h(in)g(a)f(di\256eren)-36 b(t)433 b(con)-36 b(text,)434 b(see)f(Chalice)i([)p 0 1 0 0 TeXcolorcmyk(6)p (#cite.derivatives) [[459 212 465 224] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)p Black 800 58809 a Fe(De\257nition)500 b(4.1.)p Black 554 w Fl(W)-108 b(e)433 b(de\257ne)g(the)g(\257rst)g (di\256erence)g(of)h(a)g(\257nite)f(or)g(in\257nite)g(w)-36 b(ord)434 b Fj(w)469 b Fl(to)433 b(b)36 b(e)434 b(the)f(w)-36 b(ord)14743 61743 y(\242)p Fj(w)404 b Fl(=)369 b(\()p Fj(w)19978 61942 y Fg(1)20503 61743 y Fl(\(2\))295 b Fk(\241)h Fj(w)24719 61942 y Fg(1)25244 61743 y Fl(\(1\)\)\()p Fj(w)28848 61942 y Fg(1)29373 61743 y Fl(\(3\))f Fk(\241)h Fj(w)33589 61942 y Fg(1)34114 61743 y Fl(\(2\)\))221 b Fk(\242)g(\242)g(\242)444 b Fj(;)800 64676 y Fl(where)434 b(subtraction)e(is)i(in)-36 b(terpreted)432 b(mo)36 b(dulo)434 b(2.)2751 67388 y(Note)398 b(that)f Fk(j)p Fl(\242)p Fj(w)36 b Fk(j)369 b Fl(=)f Fk(j)p Fj(w)36 b Fk(j)222 b(\241)g Fl(1)398 b(for)g Fj(w)433 b Fl(of)398 b(\257nite)f(length.)567 b(The)397 b(follo)-36 b(wing)400 b(lemma)e(relates)g(the)g(concept)800 68993 y(of)546 b(a)g(\257rst)e(di\256erence)h(to)g(that)g(of)h(the)f(c) -36 b(hange)545 b(sequence)g(in)-36 b(tro)36 b(duced)544 b(in)i(Section)p 0 1 0 0 TeXcolorcmyk 545 w(3)p (#section.3) [[465 96 471 108] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)913 b(The)546 b(pro)36 b(of)546 b(is)800 70598 y(trivial.)p Black 26475 74617 a(5)p Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Fe(Lemma)499 b(4.1.)p Black 554 w Fd(L)-66 b(et)464 b Fj(w)500 b Fd(b)-66 b(e)464 b(a)i(wor)-66 b(d.)597 b(Then)464 b Fl(\242)p Fj(w)36 b Fl(\()p Fj(i)p Fl(\))368 b(=)h(1)465 b Fd(if)f(and)h(only)g(if)f Fj(i)368 b Fk(2)h Fj(C)39665 1623 y Fh(w)40419 1424 y Fd(.)2751 3738 y Fl(Recall)455 b(the)e(sum)f(op)36 b(erator)454 b Fk(\251)p Fl(,)459 b(de\257ned)452 b(in)h(Section)p 0 1 0 0 TeXcolorcmyk 453 w(2)p (#section.2) [[337 683 343 695] [1 1 1 [3 3]] [0 0 1]] pdfm Black 454 w(as)h(the)f(term-wise)g(addition)g(of)h(t)-36 b(w)g(o)454 b(w)-36 b(ords)800 5343 y(mo)36 b(dulo)417 b(2.)573 b(The)416 b(next)h(lemma)g(states)g(the)f(relationship)g(b)36 b(et)-36 b(w)g(een)416 b(the)g(\257rst)g(di\256erence)g(of)i(a)e(sum)h (and)800 6948 y(the)433 b(sum)g(of)h(the)g(\257rst)e(di\256erences:)p Black 800 9261 a Fe(Lemma)499 b(4.2.)p Black 554 w Fd(L)-66 b(et)464 b Fj(w)12146 9460 y Fg(1)13136 9261 y Fd(and)h Fj(w)16590 9460 y Fg(2)17581 9261 y Fd(b)-66 b(e)464 b(\257nite)f(wor)-66 b(ds.)598 b(Then)464 b Fl(\242\()p Fj(w)32637 9460 y Fg(1)33458 9261 y Fk(\251)295 b Fj(w)35716 9460 y Fg(2)36242 9261 y Fl(\))368 b(=)h(\242)p Fj(w)40511 9460 y Fg(1)41332 9261 y Fk(\251)295 b Fl(\242)p Fj(w)44674 9460 y Fg(2)45200 9261 y Fd(.)2751 11575 y Fl(W)-108 b(e)625 b(no)-36 b(w)626 b(turn)e(to)h(the)g(\257rst)f(di\256erences)h (of)g(\257xed)g(p)36 b(oin)-36 b(ts)625 b Fe(w)p Fl(.)1154 b(Notice,)674 b(for)625 b(example,)675 b(that)624 b(if)800 13180 y Fj(w)405 b Fl(=)368 b(011010,)436 b(then)d(\242)p Fj(w)404 b Fl(=)369 b(10111.)580 b(No)-36 b(w)434 b(consider)11204 15649 y Fj(\301)11974 15848 y Fh(w)12728 15649 y Fl(\()p Fj(w)36 b Fl(\))368 b(=)h(011010)436 b(100101)f(100101)h(011010)f (100101)h(011010)p Fj(:)800 18117 y Fl(Computing)d(the)g(\257rst)g (di\256erence)g(of)h Fj(\301)20581 18316 y Fh(w)21336 18117 y Fl(\()p Fj(w)36 b Fl(\),)433 b(w)-36 b(e)433 b(obtain)5533 20586 y(\242\()p Fj(\301)7893 20785 y Fh(w)8646 20586 y Fl(\()p Fj(w)36 b Fl(\)\))368 b(=)h(10111)435 b(1)p 16564 20798 651 54 v 434 w(10111)g(0)p 21333 20798 V 434 w(10111)g(1)p 26102 20798 V 434 w(10111)g(1)p 30871 20798 V 434 w(10111)h(1)p 35641 20798 V 433 w(10111)11498 22523 y(=)369 b(\242)p Fj(w)469 b Fl(\242)p Fj(w)36 b Fl(\(1\))p 15362 23068 3712 54 v 433 w(\242)p Fj(w)469 b Fl(\242)p Fj(w)36 b Fl(\(2\))p 21990 23068 V 433 w(\242)p Fj(w)469 b Fl(\242)p Fj(w)36 b Fl(\(3\))p 28618 23068 V 432 w(\242)p Fj(w)469 b Fl(\242)p Fj(w)36 b Fl(\(4\))p 35245 23068 V 433 w(\242)p Fj(w)469 b Fl(\242)p Fj(w)36 b Fl(\(5\))p 41873 23068 V 433 w(\242)p Fj(w)11498 24687 y Fl(=)369 b Fj(\303)13725 24886 y Fg(\242)p Fh(w)15263 24687 y Fl(\(\242)p Fj(w)36 b Fl(\)\242)p Fj(w)g(;)800 27156 y Fl(where)518 b Fj(\303)5488 27355 y Fg(\242)p Fh(w)7544 27156 y Fl(is)g(the)f(map)h(in)-36 b(tro)36 b(duced)517 b(in)h(Section)p 0 1 0 0 TeXcolorcmyk 517 w(2)p (#section.2) [[316 473 321 485] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)832 b(It)518 b(is)g(not)g(hard)f(to)h(see)g(that)g(the)f (latter)h(w)-36 b(ord)800 28761 y Fj(\303)1646 28960 y Fg(\242)p Fh(w)3184 28761 y Fl(\(\242)p Fj(w)36 b Fl(\)\242)p Fj(w)657 b Fl(agrees)623 b(with)g(the)f(w)-36 b(ord)622 b Fj(\303)22846 28960 y Fg(\242)p Fh(w)24384 28761 y Fl(\()p Fj(\303)25736 28960 y Fg(\242)p Fh(w)27274 28761 y Fl(\(\242)p Fj(w)36 b Fl(\(1\)\)\))622 b(in)g(all)h(but)f(the)g(righ) -36 b(tmost)622 b(p)36 b(osition.)800 30366 y(Since)400 b Fj(\301)4933 29884 y Fi(1)4933 30694 y Fh(w)5929 30366 y Fl(\(0\))369 b(=)f Fe(w)401 b Fl(and)f Fj(\303)14210 29884 y Fi(1)14162 30702 y Fg(\242)p Fh(w)15700 30366 y Fl(\(\242)p Fj(w)36 b Fl(\(1\)\))368 b(=)g(\(\242)p Fj(w)36 b Fl(\))25234 30565 y Fi(\244)25759 30366 y Fl(,)407 b(this)400 b(suggests)h(the)e(follo)-36 b(wing)403 b(connection)d(b)36 b(et)-36 b(w)g(een)800 31971 y(\242)p Fe(w)434 b Fl(and)f(\(\242)p Fj(w)36 b Fl(\))8988 32170 y Fi(\244)9513 31971 y Fl(:)p Black 800 34285 a Fe(Theorem)745 b(4.1.)p Black 664 w Fd(L)-66 b(et)660 b Fj(w)697 b Fd(b)-66 b(e)661 b(a)h(wor)-66 b(d)662 b(with)f Fk(j)p Fj(w)36 b Fk(j)733 b Fl(=)g Fj(b)g Fk(\270)g Fl(2)662 b Fd(and)g Fj(w)36 b Fl(\(1\))733 b(=)f Fj(w)36 b Fl(\()p Fj(b)p Fl(\))733 b(=)g(0)p Fd(.)1187 b(Then)661 b(the)800 35890 y(\257rst)500 b(di\256er)-66 b(enc)g(e)499 b(of)h(the)h(\257xe)-66 b(d)500 b(p)-66 b(oint)499 b(of)i(the)f(morphism)h Fj(\301)30171 36089 y Fh(w)31426 35890 y Fd(is)f(exactly)h(the)f(\257xe)-66 b(d)500 b(p)-66 b(oint)499 b(of)i Fj(\303)48162 36089 y Fg(\242)p Fh(w)49700 35890 y Fd(,)509 b(i.e.,)800 37495 y Fl(\242)p Fe(w)390 b Fl(=)369 b(\(\242)p Fj(w)36 b Fl(\))7796 37694 y Fi(\244)8320 37495 y Fd(.)p Black 800 39808 a(Pr)-66 b(o)g(of.)p Black 649 w Fl(It)434 b(is)g(su\261cien)-36 b(t)432 b(to)i(sho)-36 b(w)434 b(that)f(\242)p Fe(w)p Fl(\()p Fj(i)p Fl(\))368 b(=)h(1)434 b(if)g(and)f(only)i(if)f(\(\242)p Fj(w)36 b Fl(\))37964 40007 y Fi(\244)38489 39808 y Fl(\()p Fj(i)p Fl(\))368 b(=)h(1.)2751 41414 y Fd(Case)428 b(1)p Fl(.)565 b Fj(i)369 b Fk(6\264)g Fl(0)590 b(\(mo)36 b(d)443 b Fj(b)p Fl(\).)565 b(Then)392 b(w)-36 b(e)394 b(ha)-36 b(v)g(e)393 b Fj(i)368 b Fl(=)h Fj(bk)257 b Fl(+)212 b Fj(r)36 b Fl(,)402 b(where)393 b Fj(k)414 b Fk(\270)369 b Fl(0)394 b(and)e(1)369 b Fk(\267)h Fj(r)405 b Fk(\267)369 b Fj(b)212 b Fk(\241)g Fl(1.)566 b(By)394 b(the)800 43019 y(construction)459 b(of)h(\(\242)p Fj(w)36 b Fl(\))12845 43218 y Fi(\244)13829 43019 y Fl(w)-36 b(e)459 b(ha)-36 b(v)g(e)460 b(\(\242)p Fj(w)36 b Fl(\))21856 43218 y Fi(\244)22381 43019 y Fl(\()p Fj(i)p Fl(\))412 b(=)g(1)460 b(if)g(and)f(only)h(if)g(\242)p Fj(w)36 b Fl(\()p Fj(r)g Fl(\))412 b(=)g(1.)656 b(By)460 b(Lemma)p 0 1 0 0 TeXcolorcmyk 459 w(4.1)p (#lemma.4.1) [[509 330 524 342] [1 1 1 [3 3]] [0 0 1]] pdfm Black 460 w(this)800 44624 y(holds)409 b(if)h(and)f(only)h(if)h Fj(r)405 b Fk(2)368 b Fj(C)15027 44823 y Fh(w)15781 44624 y Fl(.)571 b(As)409 b(in)g(the)g(pro)36 b(of)410 b(of)h(Theorem)p 0 1 0 0 TeXcolorcmyk 409 w(3.1)p (#theorem.3.1) [[366 315 380 327] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)416 b(w)-36 b(e)409 b(see)h(that)f Fj(r)c Fk(2)369 b Fj(C)44994 44823 y Fh(w)46157 44624 y Fl(holds)409 b(if)i(and)800 46229 y(only)444 b(if)f Fj(i)385 b Fl(=)g Fj(bk)347 b Fl(+)301 b Fj(r)421 b Fk(2)385 b Fj(C)13189 46428 y Fc(w)14027 46229 y Fl(.)607 b(Hence,)445 b(\(\242)p Fj(w)36 b Fl(\))22295 46428 y Fi(\244)22820 46229 y Fl(\()p Fj(i)p Fl(\))385 b(=)f(1)444 b(holds)e(if)i(and)f(only)g(if)h Fj(i)385 b Fk(2)f Fj(C)41399 46428 y Fc(w)42238 46229 y Fl(,)445 b(whic)-36 b(h)443 b(b)-36 b(y)443 b(Lemma)p 0 1 0 0 TeXcolorcmyk 800 47834 a(4.1)p (#lemma.4.1) [[79 286 94 298] [1 1 1 [3 3]] [0 0 1]] pdfm Black 435 w(is)433 b(equiv)-72 b(alen)-36 b(t)435 b(to)e(\242)p Fe(w)p Fl(\()p Fj(i)p Fl(\))369 b(=)f(1.)2751 49439 y Fd(Case)491 b(2)p Fl(.)663 b Fj(i)416 b Fk(\264)h Fl(0)591 b(\(mo)36 b(d)442 b Fj(b)p Fl(\).)662 b(Then)462 b Fj(i)416 b Fl(=)g Fj(b)22993 48957 y Fh(j)23480 49439 y Fj(m)462 b Fl(for)g(some)g Fj(j)491 b Fk(\270)417 b Fl(0,)469 b(with)462 b Fj(m)417 b Fk(6\264)f Fl(0)591 b(\(mo)36 b(d)443 b Fj(b)p Fl(\).)662 b(No)-36 b(w)462 b(as)g(in)800 51044 y(the)439 b(pro)36 b(of)439 b(of)h(Theorem)p 0 1 0 0 TeXcolorcmyk 439 w(3.1)p (#theorem.3.1) [[193 258 208 270] [1 1 1 [3 3]] [0 0 1]] pdfm Black 441 w(w)-36 b(e)439 b(see)g(that)g Fj(b)22938 50562 y Fh(j)23425 51044 y Fj(m)378 b Fk(2)g Fj(C)27136 51243 y Fc(w)28413 51044 y Fl(\(i.e.,)442 b(\242)p Fe(w)p Fl(\()p Fj(b)34605 50562 y Fh(j)35092 51044 y Fj(m)p Fl(\))378 b(=)g(1\))439 b(if)h(and)f(only)g(if)h Fj(m)378 b Fk(2)g Fj(C)51600 51243 y Fc(w)52439 51044 y Fl(.)800 52649 y(Since)531 b Fj(m)k Fk(6\264)g Fl(0)591 b(\(mo)36 b(d)443 b Fj(b)p Fl(\),)555 b(b)-36 b(y)532 b(Case)g(1)f(w)-36 b(e)532 b(ha)-36 b(v)g(e)531 b Fj(m)k Fk(2)g Fj(C)29625 52848 y Fc(w)30995 52649 y Fl(if)d(and)f(only)h(if)g(\(\242)p Fj(w)36 b Fl(\))42216 52848 y Fi(\244)42740 52649 y Fl(\()p Fj(m)p Fl(\))535 b(=)g(1.)872 b(By)532 b(the)800 54254 y(construction)433 b(of)h(\(\242)p Fj(w)36 b Fl(\))12793 54453 y Fi(\244)13752 54254 y Fl(w)-36 b(e)434 b(see)f(that)g(the)g (latter)h(is)g(equiv)-72 b(alen)-36 b(t)434 b(to)g(\(\242)p Fj(w)36 b Fl(\))38506 54453 y Fi(\244)39031 54254 y Fl(\()p Fj(i)p Fl(\))368 b(=)h(1.)p 51860 54254 45 878 v 51905 53421 781 45 v 51905 54254 V 52684 54254 45 878 v 800 58623 a Fm(5)2152 b(P)-60 b(alindromes)800 61543 y Fl(W)-108 b(e)614 b(no)-36 b(w)613 b(turn)f(our)i(atten)-36 b(tion)612 b(to)i(palindromes.)1118 b(Recall)615 b(that)e(the)g(complemen)-36 b(t)p 44531 60812 966 54 v 612 w Fj(w)649 b Fl(is)614 b(the)f(w)-36 b(ord)800 63148 y(obtained)487 b(b)-36 b(y)487 b(in)-36 b(terc)g(hanging)486 b(0)h(and)g(1)g(in)g Fj(w)36 b Fl(.)738 b(If)488 b Fk(j)p Fj(w)36 b Fk(j)487 b Fl(is)g(\257nite,)500 b(then)486 b(w)-36 b(e)487 b(de\257ne)f(the)h Fd(r)-66 b(eversal)624 b Fj(w)50388 62666 y Fh(R)51644 63148 y Fl(to)800 64753 y(b)36 b(e)433 b(the)g(w)-36 b(ord)434 b Fj(w)469 b Fl(written)433 b(\\bac)-36 b(kw)g(ards";)435 b(that)e(is,)h(for)h Fk(j)p Fj(w)36 b Fk(j)368 b Fl(=)h Fj(b)p Fl(,)17586 67222 y Fj(w)18552 66674 y Fh(R)19690 67222 y Fl(=)g Fj(w)36 b Fl(\()p Fj(b)p Fl(\))p Fj(w)g Fl(\()p Fj(b)294 b Fk(\241)h Fl(1\))221 b Fk(\242)g(\242)g(\242)i Fj(w)36 b Fl(\(2\))p Fj(w)g Fl(\(1\))p Fj(:)2751 69691 y Fl(The)414 b(complemen)-36 b(t)414 b(and)g(rev)-36 b(ersal)415 b(op)36 b(erations)415 b(ha)-36 b(v)g(e)415 b(the)e(follo)-36 b(wing)417 b(prop)36 b(erties,)418 b(whose)d(pro)36 b(ofs)415 b(are)800 71296 y(immediate)434 b(from)g(the)f(de\257nitions.)p Black 26475 74617 a(6)p Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Fe(Prop)42 b(osition)500 b(5.1.)p Black Black 1940 4118 a Fd(\(i\))p Black 651 w Fl(\()p 4558 3387 966 54 v Fj(w)35 b Fl(\))6029 3636 y Fh(R)7167 4118 y Fl(=)p 8548 2970 1736 54 v 369 w Fj(w)9514 3734 y Fh(R)10283 4118 y Fd(.)p Black 1542 6824 a(\(ii\))p Black 650 w Fl(\()p Fj(w)5524 6342 y Fh(R)6293 6824 y Fl(\))6799 6342 y Fh(R)7937 6824 y Fl(=)p 9317 5827 966 54 v 9317 6093 V 368 w Fj(w)405 b Fl(=)369 b Fj(w)36 b Fd(.)p Black 1143 9530 a(\(iii\))p Black 650 w Fl(\(\242)p Fj(w)g Fl(\))7114 9048 y Fh(R)8251 9530 y Fl(=)369 b(\242\()p Fj(w)12188 9048 y Fh(R)12957 9530 y Fl(\))464 b Fd(.)p Black 1342 12236 a(\(iv\))p Black 651 w Fl(\()p Fj(w)5488 12435 y Fg(1)6013 12236 y Fj(w)6943 12435 y Fg(2)7690 12236 y Fk(\242)221 b(\242)g(\242)h Fj(w)10391 12435 y Fh(n)11017 12236 y Fl(\))11523 11754 y Fh(R)12661 12236 y Fl(=)369 b Fj(w)15008 11754 y Fh(R)14972 12565 y(n)15777 12236 y Fj(w)16743 11754 y Fh(R)16707 12565 y(n)p Fi(\241)p Fg(1)18757 12236 y Fk(\242)221 b(\242)g(\242)h Fj(w)21494 11754 y Fh(R)21458 12565 y Fg(1)22263 12236 y Fd(.)p Black 800 14930 a Fe(De\257nition)663 b(5.1.)p Black 627 w Fl(A)576 b Fd(p)-66 b(alindr)g(ome)674 b Fl(is)576 b(a)h(w)-36 b(ord)576 b Fj(w)611 b Fl(suc)-36 b(h)576 b(that)f Fj(w)33888 14448 y Fh(R)35269 14930 y Fl(=)611 b Fj(w)36 b Fl(.)1005 b(A)576 b Fd(skew-p)-66 b(alindr)g(ome)674 b Fl(is)577 b(a)800 16535 y(w)-36 b(ord)458 b Fj(v)506 b Fl(suc)-36 b(h)458 b(that)g Fj(v)11654 16053 y Fh(R)12834 16535 y Fl(=)p 14257 15804 677 54 v 411 w Fj(v)47 b Fl(.)653 b(If)459 b(a)g(w)-36 b(ord)459 b(is)f(either)g(a)h(palindrome)f(or)h(a) g(sk)-36 b(ew-palindrome,)465 b(then)457 b(it)i(is)800 18140 y(said)513 b(to)g(b)36 b(e)513 b(a)g Fd(quasi-p)-66 b(alindr)g(ome)p Fl(.)815 b(W)-108 b(e)513 b(denote)f(the)g(sets)h(of)h (palindromes,)532 b(sk)-36 b(ew-palindromes,)534 b(and)800 19745 y(quasi-palindromes)434 b(b)-36 b(y)433 b Fk(P)109 b Fl(,)434 b Fk(S)100 b Fl(,)434 b(and)f Fk(Q)p Fl(,)h(resp)36 b(ectiv)-36 b(ely)-108 b(.)2751 22439 y(F)g(or)549 b(example,)579 b(the)548 b(w)-36 b(ords)549 b(0110110)j(and)c(011001)j(are)f(b)36 b(oth)548 b(quasi-palindromes.)925 b(Sp)36 b(eci\257cally)-108 b(,)800 24045 y(the)433 b(w)-36 b(ord)434 b(0110110)h(is)f(a)g (palindrome)g(and)f(the)g(w)-36 b(ord)433 b(011001)j(is)e(a)g(sk)-36 b(ew-palindrome.)p Black 800 26739 a Fe(Prop)42 b(osition)500 b(5.2.)p Black 554 w Fd(L)-66 b(et)464 b Fj(w)500 b Fd(and)465 b Fj(v)512 b Fd(b)-66 b(e)464 b(wor)-66 b(ds)466 b(of)f(lengths)f Fj(b)h Fd(and)g Fj(c)p Fd(,)f(r)-66 b(esp)g(e)g(ctively.)595 b(Then:)p Black 1940 29433 a(\(i\))p Black 651 w Fj(w)404 b Fk(2)369 b(P)574 b Fd(if)464 b(and)h(only)f(if)g Fj(w)36 b Fl(\()p Fj(i)p Fl(\))368 b(=)h Fj(w)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(i)f Fl(+)f(1\))465 b Fd(for)g Fl(1)369 b Fk(\267)h Fj(i)e Fk(\267)h Fj(b)p Fd(.)p Black 1542 32139 a(\(ii\))p Black 650 w Fj(v)416 b Fk(2)369 b(S)565 b Fd(if)464 b(and)g(only)h(if)f Fj(v)48 b Fl(\()p Fj(j)75 b Fl(\))368 b Fk(6)p Fl(=)h Fj(v)48 b Fl(\()p Fj(c)294 b Fk(\241)h Fj(j)370 b Fl(+)295 b(1\))465 b Fd(for)g Fl(1)369 b Fk(\267)g Fj(j)444 b Fk(\267)369 b Fj(c)p Fd(.)p Black 1143 34845 a(\(iii\))p Black 650 w Fj(v)416 b Fk(2)369 b(S)565 b Fd(implies)464 b(that)g Fk(j)p Fj(v)48 b Fk(j)465 b Fd(is)g(even.)p Black 1342 37551 a(\(iv\))p Black 651 w Fj(w)404 b Fk(2)369 b(P)574 b Fd(if)464 b(and)h(only)f(if)g Fj(w)331 b Fk(\251)295 b Fj(w)19564 37069 y Fh(R)20702 37551 y Fl(=)369 b(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)p Fd(;)465 b Fj(v)416 b Fk(2)369 b(S)565 b Fd(if)464 b(and)h(only)g(if)e Fj(w)331 b Fk(\251)296 b Fj(w)41985 37069 y Fh(R)43122 37551 y Fl(=)369 b(11)221 b Fk(\242)g(\242)g(\242)i Fl(1)p Fd(.)p Black 1741 40257 a(\(v\))p Black 651 w Fk(P)404 b(\\)295 b(S)469 b Fl(=)368 b Fk(;)p Fd(.)p Black 800 42951 a(Pr)-66 b(o)g(of.)p Black 649 w Fl(\(i\))387 b(and)g(\(ii\))g (follo)-36 b(w)389 b(from)e(De\257nition)p 0 1 0 0 TeXcolorcmyk 387 w(5.1)p (#definition.5.1) [[288 330 303 342] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)564 b(T)-108 b(o)387 b(pro)-36 b(v)g(e)387 b(\(iii\),)398 b(observ)-36 b(e)387 b(that)f(if)i Fk(j)p Fj(v)48 b Fk(j)369 b Fl(=)f Fj(c)387 b Fl(w)-36 b(ere)387 b(o)36 b(dd,)800 44556 y(then)497 b Fj(v)48 b Fl(\()p Fj(j)75 b Fl(\))477 b(=)h Fj(v)48 b Fl(\()p Fj(c)338 b Fk(\241)h Fj(j)414 b Fl(+)339 b(1\))498 b(for)g Fj(j)553 b Fl(=)478 b Fk(d)p Fj(c=)p Fl(2)p Fk(e)p Fl(,)516 b(whic)-36 b(h)498 b(violates)h(\(ii\).) 771 b(The)498 b(last)h(t)-36 b(w)g(o)498 b(prop)36 b(erties)497 b(follo)-36 b(w)800 46161 y(from)434 b(\(i\))g(and)f(\(ii\).)p 51860 46161 45 878 v 51905 45327 781 45 v 51905 46161 V 52684 46161 45 878 v 2751 48756 a(Recall)i(that)e(the)g(pro)36 b(duct)433 b(of)h(t)-36 b(w)g(o)434 b(w)-36 b(ords)433 b Fj(w)469 b Fl(and)433 b Fj(v)481 b Fl(is)434 b(de\257ned)e(b)-36 b(y)22506 51669 y Fj(w)330 b Fk(\243)296 b Fj(v)416 b Fl(=)369 b Fj(\301)28291 51868 y Fh(w)29045 51669 y Fl(\()p Fj(v)48 b Fl(\))p Fj(:)800 54581 y Fl(Giv)-36 b(en)565 b(t)-36 b(w)g(o)566 b(sets)g(of)g(w)-36 b(ords)565 b Fk(U)698 b Fl(and)565 b Fk(V)109 b Fl(,)599 b(w)-36 b(e)566 b(let)g Fk(U)517 b(\243)385 b(V)675 b Fl(denote)565 b(the)g(set)g(of)h (all)h(w)-36 b(ords)565 b Fj(u)386 b Fk(\243)f Fj(v)48 b Fl(,)598 b(with)800 56186 y Fj(u)417 b Fk(2)e(U)594 b Fl(and)461 b Fj(v)j Fk(2)416 b(V)109 b Fl(.)662 b(W)-108 b(e)461 b(sho)-36 b(w)461 b(that)g(quasi-palindromes)h(are)f(closed)h (with)g(resp)36 b(ect)461 b(to)g(this)g(pro)36 b(duct)800 57791 y(op)g(eration.)p Black 800 60485 a Fe(Prop)42 b(osition)583 b(5.3.)p Black 591 w Fd(L)-66 b(et)531 b Fj(w)567 b Fd(and)532 b Fj(v)579 b Fd(b)-66 b(e)531 b(\257nite)f(wor)-66 b(ds.)798 b(Then)532 b Fj(w)36 b Fd(,)p Fj(v)539 b Fk(2)492 b(Q)532 b Fd(if)e(and)i(only)g(if)e Fj(w)380 b Fk(\243)345 b Fj(v)540 b Fk(2)493 b(Q)p Fd(.)800 62090 y(Mor)-66 b(e)g(over,)463 b(we)i(have)g(the)g(fol)66 b(lowing)464 b(c)-66 b(ontainment)462 b(r)-66 b(elations:)23372 65003 y Fk(P)405 b(\243)295 b(P)478 b(\275)369 b(P)109 b Fj(;)19899 b Fl(\(5.1\))23501 66940 y Fk(P)405 b(\243)295 b(S)469 b(\275)369 b(S)100 b Fj(;)20028 b Fl(\(5.2\))23501 68877 y Fk(S)396 b(\243)295 b(P)478 b(\275)369 b(S)100 b Fj(;)20028 b Fl(\(5.3\))23631 70814 y Fk(S)395 b(\243)295 b(S)469 b(\275)369 b(P)109 b Fj(:)19899 b Fl(\(5.4\))p Black 26475 74617 a(7)p Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Fd(Pr)-66 b(o)g(of.)p Black 649 w Fl(Supp)36 b(ose)433 b(\257rst)f(that)i Fj(w)36 b Fl(,)p Fj(v)416 b Fk(2)368 b(P)543 b Fl(with)434 b Fk(j)p Fj(w)36 b Fk(j)368 b Fl(=)h Fj(b)433 b Fl(and)g Fk(j)p Fj(v)48 b Fk(j)369 b Fl(=)f Fj(c)p Fl(.)579 b(Then)18483 4255 y Fj(w)330 b Fk(\243)296 b Fj(v)416 b Fl(=)369 b Fj(\301)24268 4454 y Fh(w)25022 4255 y Fl(\()p Fj(v)48 b Fl(\))368 b(=)h Fj(w)29390 4454 y Fg(1)29915 4255 y Fj(w)30845 4454 y Fg(2)31592 4255 y Fk(\242)221 b(\242)g(\242)h Fj(w)34293 4454 y Fh(c)34756 4255 y Fj(;)800 7087 y Fl(with)381 b Fj(w)4640 7286 y Fh(i)5384 7087 y Fl(=)369 b Fj(\301)7535 7286 y Fh(w)8289 7087 y Fl(\()p Fj(v)48 b Fl(\()p Fj(i)p Fl(\)\))379 b(for)j(1)369 b Fk(\267)g Fj(i)g Fk(\267)g Fj(c)p Fl(.)560 b(Notice)382 b(for)f(eac)-36 b(h)381 b Fj(i)f Fl(that)h(w)-36 b(e)381 b(ha)-36 b(v)g(e)381 b Fj(w)38031 7286 y Fh(i)38775 7087 y Fk(2)369 b(f)p Fj(w)36 b(;)p 42242 6356 966 54 v 221 w(w)g Fk(g)369 b(\275)g(P)109 b Fl(.)561 b(Applying)800 8692 y(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.1)p (#proposition.5.1) [[142 639 157 651] [1 1 1 [3 3]] [0 0 1]] pdfm Black 435 w(\(iv\),)434 b(w)-36 b(e)434 b(obtain)10191 11523 y(\()p Fj(\301)11467 11722 y Fh(w)12221 11523 y Fl(\()p Fj(v)48 b Fl(\)\))294 b Fk(\251)h Fl(\()p Fj(\301)17314 11722 y Fh(w)18068 11523 y Fl(\()p Fj(v)48 b Fl(\)\))20263 10975 y Fh(R)21401 11523 y Fl(=)368 b Fj(w)23711 11722 y Fg(1)24237 11523 y Fj(w)25167 11722 y Fg(2)25914 11523 y Fk(\242)221 b(\242)g(\242)h Fj(w)28615 11722 y Fh(c)29373 11523 y Fk(\251)295 b Fj(w)31667 10975 y Fh(R)31631 11852 y(c)32436 11523 y Fj(w)33402 10975 y Fh(R)33366 11852 y(c)p Fi(\241)p Fg(1)35252 11523 y Fk(\242)221 b(\242)g(\242)i Fj(w)37990 10975 y Fh(R)37954 11852 y Fg(1)21401 13601 y Fl(=)368 b(\()p Fj(w)24217 13800 y Fg(1)25038 13601 y Fk(\251)295 b Fj(w)27332 13053 y Fh(R)27296 13930 y(c)28101 13601 y Fl(\)\()p Fj(w)30043 13800 y Fg(2)30864 13601 y Fk(\251)g Fj(w)33158 13053 y Fh(R)33122 13930 y(c)p Fi(\241)p Fg(1)34787 13601 y Fl(\))221 b Fk(\242)g(\242)g(\242)h Fl(\()p Fj(w)38721 13800 y Fh(c)39479 13601 y Fk(\251)295 b Fj(w)41773 13053 y Fh(R)41737 13930 y Fg(1)42542 13601 y Fl(\))p Fj(:)800 16433 y Fl(Since)433 b Fj(v)417 b Fk(2)368 b(P)109 b Fl(,)434 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.2)p (#proposition.5.2) [[210 569 225 581] [1 1 1 [3 3]] [0 0 1]] pdfm Black 435 w(\(i\))433 b(implies)20721 19264 y Fj(w)21651 19463 y Fh(i)22395 19264 y Fl(=)369 b Fj(\301)24546 19463 y Fh(w)25300 19264 y Fl(\()p Fj(v)48 b Fl(\()p Fj(i)p Fl(\)\))22395 21201 y(=)369 b Fj(\301)24546 21400 y Fh(w)25300 21201 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)294 b Fk(\241)i Fj(i)e Fl(+)h(1\)\))22395 23138 y(=)369 b Fj(w)24706 23337 y Fh(c)p Fi(\241)p Fh(i)p Fg(+1)27423 23138 y Fj(:)800 25970 y Fl(Since)433 b Fj(w)5126 26169 y Fh(i)5871 25970 y Fk(2)368 b(P)109 b Fl(,)434 b(it)g(follo)-36 b(ws)435 b(from)f(this)g(and)f(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.2)p (#proposition.5.2) [[339 483 354 495] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(\(iv\))434 b(that)19294 28801 y(\()p Fj(w)20730 29000 y Fh(i)21400 28801 y Fk(\251)295 b Fj(w)23694 28253 y Fh(R)23658 29129 y(c)p Fi(\241)p Fh(i)p Fg(+1)26375 28801 y Fl(\))369 b(=)g(\()p Fj(w)30067 29000 y Fh(i)30737 28801 y Fk(\251)296 b Fj(w)33032 28253 y Fh(R)32996 29129 y(i)33801 28801 y Fl(\))27250 30738 y(=)369 b(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)p Fj(:)800 33570 y Fl(Hence)18352 35175 y(\()p Fj(\301)19628 35374 y Fh(w)20382 35175 y Fl(\()p Fj(v)48 b Fl(\)\))295 b Fk(\251)g Fl(\()p Fj(\301)25476 35374 y Fh(w)26230 35175 y Fl(\()p Fj(v)48 b Fl(\)\))28425 34626 y Fh(R)29562 35175 y Fl(=)369 b(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)p Fj(;)800 37456 y Fl(whic)-36 b(h)500 b(implies)i(that)e Fj(\301)12726 37655 y Fh(w)13480 37456 y Fl(\()p Fj(v)48 b Fl(\))482 b Fk(2)h(P)109 b Fl(.)780 b(This)501 b(pro)-36 b(v)g(es)500 b(\()p 0 1 0 0 TeXcolorcmyk(5.1)p (#equation.5.1) [[313 380 328 392] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q(.)779 b(The)501 b(relations)g(\()p 0 1 0 0 TeXcolorcmyk(5.2)p (#equation.5.2) [[421 380 435 392] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q({\()p 0 1 0 0 TeXcolorcmyk(5.4)p (#equation.5.4) [[450 380 465 392] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(can)g(b)36 b(e)500 b(pro)-36 b(v)g(ed)800 39061 y(b)g(y)510 b(similar)i(argumen)-36 b(ts.)808 b(It)510 b(follo)-36 b(ws)513 b(from)d(\(10.1\){\(10.4\))j(that)d Fj(\301)34551 39260 y Fh(w)35305 39061 y Fl(\()p Fj(v)48 b Fl(\))499 b Fk(2)g(Q)510 b Fl(whenev)-36 b(er)511 b Fj(w)535 b Fk(2)499 b(Q)511 b Fl(and)800 40666 y Fj(v)416 b Fk(2)369 b(Q)p Fl(.)2751 42271 y(Con)-36 b(v)g(ersely)-108 b(,)435 b(supp)36 b(ose)433 b Fj(\301)15249 42470 y Fh(w)16003 42271 y Fl(\()p Fj(v)48 b Fl(\))368 b Fk(2)g(Q)p Fl(.)579 b(Then)433 b Fj(\301)25505 42470 y Fh(w)26259 42271 y Fl(\()p Fj(v)48 b Fl(\))433 b(is)h(giv)-36 b(en)434 b(b)-36 b(y)15876 45102 y Fj(\301)16646 45301 y Fh(w)17400 45102 y Fl(\()p Fj(v)48 b Fl(\))368 b(=)h Fj(\301)21608 45301 y Fh(w)22362 45102 y Fl(\()p Fj(v)48 b Fl(\(1\)\))p Fj(\301)26483 45301 y Fh(w)27236 45102 y Fl(\()p Fj(v)g Fl(\(2\)\))221 b Fk(\242)g(\242)g(\242)h Fj(\301)33349 45301 y Fh(w)34103 45102 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)p Fl(\)\))p Fj(:)800 47934 y Fl(By)434 b(de\257nition)f Fj(\301)9392 48133 y Fh(w)10146 47934 y Fl(\()p Fj(v)48 b Fl(\))368 b Fk(2)h(Q)433 b Fl(implies)h(that)f(either)21822 50765 y Fj(\301)22592 50964 y Fh(w)23347 50765 y Fl(\()p Fj(v)48 b Fl(\))368 b(=)g(\()p Fj(\301)28060 50964 y Fh(w)28814 50765 y Fl(\()p Fj(v)48 b Fl(\)\))31009 50216 y Fh(R)800 53596 y Fl(or)p 21642 54046 3213 54 v 21642 55201 a Fj(\301)22412 55400 y Fh(w)23166 55201 y Fl(\()p Fj(v)g Fl(\))368 b(=)h(\()p Fj(\301)27880 55400 y Fh(w)28634 55201 y Fl(\()p Fj(v)48 b Fl(\)\))30829 54653 y Fh(R)31597 55201 y Fj(:)800 57482 y Fl(In)433 b(particular,)h(w)-36 b(e)434 b(ha)-36 b(v)g(e)20206 59087 y Fj(\301)20976 59286 y Fh(w)21730 59087 y Fl(\()p Fj(v)48 b Fl(\(1\)\))368 b(=)h(\()p Fj(\301)28106 59286 y Fh(w)28860 59087 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)p Fl(\)\)\))32627 58539 y Fh(R)800 61368 y Fl(or)p 20025 61818 4875 54 v 20025 62973 a Fj(\301)20795 63172 y Fh(w)21549 62973 y Fl(\()p Fj(v)g Fl(\(1\)\))368 b(=)h(\()p Fj(\301)27925 63172 y Fh(w)28679 62973 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)p Fl(\)\)\))32446 62425 y Fh(R)33214 62973 y Fj(:)800 65254 y Fl(It)500 b(follo)-36 b(ws)503 b(that)d(either)g Fj(w)518 b Fl(=)483 b Fj(w)17159 64772 y Fh(R)18428 65254 y Fl(or)p 20084 64523 966 54 v 500 w Fj(w)519 b Fl(=)482 b Fj(w)23993 64772 y Fh(R)24762 65254 y Fl(,)518 b(and)499 b(in)i(an)-36 b(y)500 b(case)h(w)-36 b(e)501 b(ha)-36 b(v)g(e)501 b Fj(w)518 b Fk(2)482 b(Q)p Fl(.)779 b(It)500 b(remains)h(to)800 66859 y(b)36 b(e)464 b(sho)-36 b(wn)465 b(that)f Fj(v)470 b Fk(2)421 b(Q)p Fl(,)473 b(and)464 b(to)h(do)f(this)h(w)-36 b(e)464 b(again)i(distinguish)e(sev)-36 b(eral)466 b(cases.)672 b(Supp)36 b(ose)464 b(\257rst)f(that)800 68464 y Fj(w)405 b Fk(2)368 b(P)543 b Fl(and)433 b Fj(\301)8155 68663 y Fh(w)8909 68464 y Fl(\()p Fj(v)48 b Fl(\))368 b Fk(2)h(S)100 b Fl(.)578 b(No)-36 b(w)434 b Fj(\301)17796 68663 y Fh(w)18550 68464 y Fl(\()p Fj(v)48 b Fl(\))433 b(is)h(of)g(the)f(form)15876 71296 y Fj(\301)16646 71495 y Fh(w)17400 71296 y Fl(\()p Fj(v)48 b Fl(\))368 b(=)h Fj(\301)21608 71495 y Fh(w)22362 71296 y Fl(\()p Fj(v)48 b Fl(\(1\)\))p Fj(\301)26483 71495 y Fh(w)27236 71296 y Fl(\()p Fj(v)g Fl(\(2\)\))221 b Fk(\242)g(\242)g(\242)h Fj(\301)33349 71495 y Fh(w)34103 71296 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)p Fl(\)\))p Fj(:)p Black 26475 74617 a Fl(8)p Black eop %%Page: 9 9 9 8 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(By)434 b(our)f(assumption)h(that)f Fj(\301)15621 1623 y Fh(w)16375 1424 y Fl(\()p Fj(v)48 b Fl(\))368 b Fk(2)g(S)534 b Fl(it)434 b(follo)-36 b(ws)435 b(that)p 18149 2968 4668 54 v 18149 4124 a Fj(\301)18919 4323 y Fh(w)19673 4124 y Fl(\()p Fj(v)48 b Fl(\()p Fj(i)p Fl(\)\))368 b(=)g(\()p Fj(\301)25842 4323 y Fh(w)26596 4124 y Fl(\()p Fj(v)48 b Fl(\()p Fj(c)294 b Fk(\241)i Fj(i)f Fl(+)g(1\)\)\))34682 3575 y Fh(R)50126 4124 y Fl(\(5.5\))800 6824 y(for)374 b(1)c Fk(\267)f Fj(i)f Fk(\267)i Fj(c)p Fl(.)558 b(If)374 b Fj(v)48 b Fl(\()p Fj(i)p Fl(\))368 b(=)g(0,)387 b(then)372 b(\()p 0 1 0 0 TeXcolorcmyk(5.5)p (#equation.5.5) [[241 656 256 668] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))i(and)g(our)f(assumption)g Fj(w)405 b Fk(2)368 b(P)483 b Fl(implies)374 b(that)f Fj(v)48 b Fl(\()p Fj(c)173 b Fk(\241)g Fj(i)g Fl(+)g(1\))367 b(=)h(1.)800 8429 y(Lik)-36 b(ewise,)437 b Fj(v)48 b Fl(\()p Fj(i)p Fl(\))371 b(=)g(1)435 b(implies)h(that)f Fj(v)48 b Fl(\()p Fj(c)295 b Fk(\241)h Fj(i)g Fl(+)g(1\))372 b(=)f(0.)584 b(Hence)435 b(w)-36 b(e)435 b(ha)-36 b(v)g(e)436 b Fj(v)48 b Fl(\()p Fj(i)p Fl(\))370 b Fk(6)p Fl(=)h Fj(v)48 b Fl(\()p Fj(c)296 b Fk(\241)g Fj(i)g Fl(+)g(1\))435 b(for)h(all)g Fj(i)p Fl(,)800 10034 y(so)e Fj(v)416 b Fk(2)369 b(S)534 b Fl(b)-36 b(y)433 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.2)p (#proposition.5.2) [[206 627 220 639] [1 1 1 [3 3]] [0 0 1]] pdfm Black 435 w(\(ii\).)578 b(The)434 b(pro)36 b(ofs)434 b(of)g(the)f(remaining)h(cases)g(are)g(similar.)p 51860 10034 45 878 v 51905 9200 781 45 v 51905 10034 V 52684 10034 45 878 v 2751 12569 a(W)-108 b(e)434 b(no)-36 b(w)433 b(c)-36 b(haracterize)434 b(\257rst)f(di\256erences)g(of)h (palindromes.)p Black 800 15080 a Fe(Lemma)672 b(5.1.)p Black 631 w Fd(Given)602 b(a)i(\257nite)d(wor)-66 b(d)604 b Fj(w)660 b Fk(2)625 b Fl(\247)25233 14598 y Fi(\244)26363 15080 y Fd(with)603 b Fk(j)p Fj(w)36 b Fk(j)625 b(\270)g Fl(2)p Fd(,)638 b(we)603 b(have)h Fj(w)660 b Fk(2)625 b(Q)603 b Fd(if)g(and)g(only)g(if)800 16685 y Fl(\242)p Fj(w)404 b Fk(2)369 b(P)109 b Fd(.)p Black 800 19197 a(Pr)-66 b(o)g(of.)p Black 649 w Fl(Applying)434 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.2)p (#proposition.5.2) [[230 544 245 556] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(\(iv\),)435 b(it)e(follo)-36 b(ws)436 b(that)d(\242)p Fj(w)404 b Fk(2)369 b(P)543 b Fl(is)434 b(equiv)-72 b(alen)-36 b(t)434 b(to)10959 21897 y(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)369 b(=)g(\242)p Fj(w)330 b Fk(\251)296 b Fl(\(\242)p Fj(w)36 b Fl(\))23387 21349 y Fh(R)15271 23975 y Fl(=)369 b(\242)p Fj(w)330 b Fk(\251)296 b Fl(\242\()p Fj(w)22881 23427 y Fh(R)23649 23975 y Fl(\))10159 b(\(Prop.)p 0 1 0 0 TeXcolorcmyk 433 w(5)p Fj(:)p Fl(1)p (#proposition.5.1) [[417 501 432 513] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\(iii)r(\)\))15271 26053 y(=)369 b(\242\()p Fj(w)330 b Fk(\251)295 b Fj(w)21796 25504 y Fh(R)22566 26053 y Fl(\))11892 b(\(Lemma)p 0 1 0 0 TeXcolorcmyk 433 w(4)p Fj(:)p Fl(2)p (#lemma.4.2) [[433 483 448 495] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))p Fj(:)800 28753 y Fl(Hence)468 b Fj(w)355 b Fk(\251)319 b Fj(w)8303 28271 y Fh(R)9540 28753 y Fl(is)469 b(either)f(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)469 b(or)f(11)221 b Fk(\242)g(\242)g(\242)i Fl(1,)478 b(and)468 b(b)-36 b(y)468 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 469 w(5.2)p (#proposition.5.2) [[404 458 419 470] [1 1 1 [3 3]] [0 0 1]] pdfm Black 469 w(\(iv\))469 b(this)f(is)h(equiv)-72 b(alen)-36 b(t)469 b(to)800 30358 y Fj(w)405 b Fk(2)368 b(Q)p Fl(.)p 51860 30358 V 51905 29524 781 45 v 51905 30358 V 52684 30358 45 878 v 2751 32892 a(W)-108 b(e)434 b(no)-36 b(w)433 b(consider)h(palindromes)f(in)h(in\257nite)e(w)-36 b(ords)434 b(of)g(the)f(form)22433 35592 y Fj(w)23363 35791 y Fi(\244)24258 35592 y Fl(=)368 b Fj(\303)26532 35044 y Fi(1)26484 35921 y Fh(w)27528 35592 y Fl(\()p Fj(w)36 b Fl(\(1\)\))800 38292 y(in)-36 b(tro)36 b(duced)432 b(in)i(Section)p 0 1 0 0 TeXcolorcmyk 433 w(2)p (#section.2) [[192 372 198 384] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)p Black 800 40804 a Fe(Lemma)615 b(5.2.)p Black 606 w Fd(L)-66 b(et)556 b Fj(w)593 b Fd(b)-66 b(e)557 b(a)h(\257nite)e(wor)-66 b(d.)876 b(If)557 b Fj(w)25690 41003 y Fi(\244)26773 40804 y Fd(c)-66 b(ontains)556 b(arbitr)-66 b(arily)556 b(long)h(p)-66 b(alindr)g(omes,)580 b(then)557 b Fj(w)800 42409 y Fd(itself)464 b(is)h(a)g(p)-66 b(alindr)g(ome.)p Black 800 44921 a(Pr)g(o)g(of.)p Black 649 w Fl(Let)433 b Fj(v)481 b Fl(b)36 b(e)434 b(a)g(sub)-36 b(w)g(ord)432 b(of)i Fj(w)18715 45120 y Fi(\244)19675 44921 y Fl(that)f(is)h(a)f(palindrome.)579 b(Then)433 b Fj(v)481 b Fl(is)434 b(of)g(the)f(form)19218 47621 y Fj(v)417 b Fl(=)368 b Fj(x)p Fl([)p Fj(u)23484 47820 y Fg(1)24011 47621 y Fl(])p Fj(w)36 b Fl([)p Fj(u)26439 47820 y Fg(2)26965 47621 y Fl(])p Fj(w)257 b Fk(\242)221 b(\242)g(\242)h Fj(w)36 b Fl([)p Fj(u)32351 47820 y Fh(n)32978 47621 y Fl(])p Fj(y)48 b(;)15744 b Fl(\(5.6\))800 50320 y(where)462 b([)p Fj(u)5687 50519 y Fh(i)6064 50320 y Fl(])h(for)g(1)418 b Fk(\267)h Fj(i)f Fk(\267)g Fj(n)463 b Fl(are)g(the)f(letters)g(\257lling)h(the)f(\\holes")h(arising)h(in)e (the)g(construction)g(of)h Fj(w)51913 50519 y Fi(\244)52439 50320 y Fl(,)800 51926 y(and)445 b Fj(x)h Fl(and)f Fj(y)494 b Fl(are)445 b(a)h(su\261x)g(and)f(pre\257x)g(of)i Fj(w)36 b Fl(,)448 b(resp)36 b(ectiv)-36 b(ely)-108 b(.)615 b(\(W)-108 b(e)446 b(allo)-36 b(w)447 b(the)e(p)36 b(ossibilit)-36 b(y)447 b(that)e Fj(x)g Fl(or)h Fj(y)800 53531 y Fl(or)434 b(b)36 b(oth)433 b(are)h(empt)-36 b(y)-108 b(.\))2751 55136 y(Supp)36 b(ose)489 b(\257rst)g(that)h Fk(j)p Fj(x)p Fk(j)465 b Fl(=)g Fk(j)p Fj(y)48 b Fk(j)p Fl(.)748 b(If)491 b(w)-36 b(e)490 b(subtract)f Fk(j)p Fj(x)p Fk(j)334 b Fl(+)f(1)491 b(letters)f(from)g(eac)-36 b(h)490 b(side)g(of)584 b(\()p 0 1 0 0 TeXcolorcmyk(5.6)p (#equation.5.6) [[497 221 512 233] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)505 b(then)800 56741 y(the)433 b(remaining)h(w)-36 b(ord)19269 58346 y Fj(v)19898 58545 y Fg(0)20793 58346 y Fl(=)368 b Fj(w)36 b Fl([)p Fj(u)24240 58545 y Fg(2)24766 58346 y Fl(])p Fj(w)g Fl([)p Fj(u)27194 58545 y Fg(3)27720 58346 y Fl(])221 b Fk(\242)g(\242)g(\242)i Fl([)p Fj(u)31175 58545 y Fh(n)p Fi(\241)p Fg(1)33004 58346 y Fl(])p Fj(w)15831 b Fl(\(5.7\))800 60570 y(is)463 b(still)h(a)f(palindrome.)665 b(Notice)464 b(that)e Fj(v)20789 60769 y Fg(0)21777 60570 y Fl(b)36 b(oth)463 b(b)36 b(egins)462 b(and)h(ends)f(with)g Fj(w)36 b Fl(.)666 b(Since)462 b Fj(v)43520 60769 y Fg(0)44465 60570 y Fk(2)418 b(P)109 b Fl(,)470 b(it)463 b(follo)-36 b(ws)800 62176 y(that)433 b Fj(w)405 b Fl(=)368 b Fj(w)7299 61693 y Fh(R)8068 62176 y Fl(,)434 b(and)f(hence)g Fj(w)405 b Fk(2)368 b(P)109 b Fl(.)2751 63781 y(No)-36 b(w)485 b(assume)g(without)f(loss)h(of)h(generalit)-36 b(y)485 b(that)f Fk(j)p Fj(x)p Fk(j)456 b Fj(>)g Fk(j)p Fj(y)48 b Fk(j)p Fl(.)731 b(Let)484 b Fk(j)p Fj(w)36 b Fk(j)455 b Fl(=)h Fj(b)p Fl(,)497 b(and)484 b(let)h Fk(j)p Fj(x)p Fk(j)456 b Fl(=)f Fj(b)330 b Fk(\241)g Fj(m)800 65386 y Fl(for)485 b(some)f Fj(m)g Fl(with)g(0)455 b Fk(\267)h Fj(m)e(<)h(b)p Fl(.)730 b(Then)483 b Fk(j)p Fj(y)48 b Fk(j)455 b Fl(=)g Fj(b)329 b Fk(\241)h Fj(m)f Fk(\241)h Fj(r)521 b Fl(for)484 b(some)h Fj(r)520 b Fl(with)484 b(1)455 b Fk(\267)h Fj(r)491 b Fk(\267)455 b Fj(b)330 b Fk(\241)f Fj(m)484 b Fl(\(since)800 66991 y Fk(j)p Fj(x)p Fk(j)448 b Fj(>)f Fk(j)p Fj(y)48 b Fk(j)p Fl(\).)716 b(No)-36 b(w)480 b(let)g Fj(x)12859 67190 y Fg(1)13865 66991 y Fl(b)36 b(e)479 b(the)g(su\261x)h(of)g Fj(x)g Fl(of)g(length)g Fk(j)p Fj(x)p Fk(j)327 b(\241)f(j)p Fj(y)48 b Fk(j)327 b(\241)f Fl(1,)492 b(so)480 b(that)f Fk(j)p Fj(x)43134 67190 y Fg(1)43660 66991 y Fk(j)448 b Fl(=)f Fj(r)363 b Fk(\241)326 b Fl(1.)717 b(If)481 b(w)-36 b(e)800 68596 y(remo)g(v)g(e)434 b Fk(j)p Fj(y)48 b Fk(j)295 b Fl(+)g(1)434 b(letters)f(from)h(eac)-36 b(h)434 b(side)f(of)i Fj(v)48 b Fl(,)433 b(then)f(the)i(resulting)f(w) -36 b(ord)19119 71296 y Fj(v)19748 71495 y Fg(1)20643 71296 y Fl(=)369 b Fj(x)22763 71495 y Fg(1)23288 71296 y Fl([)p Fj(u)24389 71495 y Fg(1)24916 71296 y Fl(])p Fj(w)36 b Fl([)p Fj(u)27344 71495 y Fg(2)27870 71296 y Fl(])221 b Fk(\242)g(\242)g(\242)i Fl([)p Fj(u)31325 71495 y Fh(n)p Fi(\241)p Fg(1)33154 71296 y Fl(])p Fj(w)15681 b Fl(\(5.8\))p Black 26475 74617 a(9)p Black eop %%Page: 10 10 10 9 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(m)-36 b(ust)433 b(still)h(b)36 b(e)433 b(a)h(palindrome.)579 b(Since)433 b Fj(x)20847 1623 y Fg(1)21806 1424 y Fl(is)h(a)g(su\261x)f (of)i Fj(w)36 b Fl(,)433 b(w)-36 b(e)434 b(can)g(write)f Fj(w)470 b Fl(as)20774 4358 y Fj(w)404 b Fl(=)369 b Fj(aw)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(r)331 b Fl(+)295 b(1\))p Fj(x)31939 4557 y Fg(1)32465 4358 y Fj(;)17300 b Fl(\(5.9\))800 7291 y(where)461 b Fj(a)g Fl(is)h(the)f(pre\257x)g(of)h Fj(w)497 b Fl(of)462 b(length)f Fj(b)314 b Fk(\241)g Fj(r)36 b Fl(,)469 b(and)461 b Fj(w)36 b Fl(\()p Fj(b)314 b Fk(\241)g Fj(r)350 b Fl(+)314 b(1\))462 b(is)f(the)g(\()p Fj(b)314 b Fk(\241)g Fj(r)351 b Fl(+)314 b(1\)st)461 b(letter)g(of)h Fj(w)36 b Fl(.)800 8896 y(Substituting)450 b(\()p 0 1 0 0 TeXcolorcmyk(5.9)p (#equation.5.9) [[151 637 166 649] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))434 b(in)-36 b(to)434 b(\()p 0 1 0 0 TeXcolorcmyk(5.8)p (#equation.5.8) [[203 637 218 649] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(w)-36 b(e)434 b(obtain)10928 11830 y Fj(v)11557 12029 y Fg(1)12452 11830 y Fl(=)368 b Fj(x)14571 12029 y Fg(1)15097 11830 y Fl([)p Fj(u)16198 12029 y Fg(1)16725 11830 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(r)331 b Fl(+)295 b(1\))p Fj(x)25536 12029 y Fg(1)26062 11830 y Fl([)p Fj(u)27163 12029 y Fg(2)27689 11830 y Fl(])221 b Fk(\242)g(\242)g(\242)i Fl([)p Fj(u)31144 12029 y Fh(n)p Fi(\241)p Fg(1)32973 11830 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)295 b Fk(\241)g Fj(r)332 b Fl(+)295 b(1\))p Fj(x)41785 12029 y Fg(1)42311 11830 y Fj(:)6804 b Fl(\(5.10\))800 14763 y(Subtracting)432 b Fj(r)332 b Fk(\241)295 b Fl(1)434 b(letters)g(from)g(eac)-36 b(h)433 b(side)h(of)527 b(\()p 0 1 0 0 TeXcolorcmyk(5.10)p (#equation.5.10) [[305 584 326 596] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))q(,)433 b(w)-36 b(e)434 b(obtain)12193 17696 y Fj(v)12822 17895 y Fg(2)13717 17696 y Fl(=)368 b([)p Fj(u)16198 17895 y Fg(1)16725 17696 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(r)331 b Fl(+)295 b(1\))p Fj(x)25536 17895 y Fg(1)26062 17696 y Fl([)p Fj(u)27163 17895 y Fg(2)27689 17696 y Fl(])221 b Fk(\242)g(\242)g(\242)i Fl([)p Fj(u)31144 17895 y Fh(n)p Fi(\241)p Fg(1)32973 17696 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)295 b Fk(\241)g Fj(r)332 b Fl(+)295 b(1\))p Fj(;)8069 b Fl(\(5.11\))800 20630 y(whic)-36 b(h)433 b(again)i(is)f(a)g(palindrome.)578 b(Since)433 b Fj(v)21705 20829 y Fg(2)22600 20630 y Fk(2)368 b(P)109 b Fl(,)434 b(it)g(follo)-36 b(ws)435 b(that)14684 23563 y([)p Fj(u)15785 23762 y Fg(1)16311 23563 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)295 b Fk(\241)g Fj(r)331 b Fl(+)295 b(1\))369 b(=)g(\([)p Fj(u)27740 23762 y Fh(n)p Fi(\241)p Fg(1)29569 23563 y Fl(])p Fj(aw)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(r)331 b Fl(+)295 b(1\)\))38147 23015 y Fh(R)24752 25641 y Fl(=)369 b Fj(w)36 b Fl(\()p Fj(b)294 b Fk(\241)i Fj(r)331 b Fl(+)295 b(1\))p Fj(a)33844 25093 y Fh(R)34613 25641 y Fl([)p Fj(u)35714 25840 y Fh(n)p Fi(\241)p Fg(1)37544 25641 y Fl(])p Fj(:)800 28575 y Fl(Hence)432 b([)p Fj(u)5765 28774 y Fg(1)6292 28575 y Fl(])369 b(=)g Fj(w)36 b Fl(\()p Fj(b)292 b Fk(\241)h Fj(r)330 b Fl(+)292 b(1\))370 b(=)e([)p Fj(u)18273 28774 y Fh(n)p Fi(\241)p Fg(1)20102 28575 y Fl(].)579 b(Pro)36 b(ceeding)432 b(inductiv)-36 b(ely)433 b(\(b)-36 b(y)433 b(remo)-36 b(ving)433 b(at)f(eac)-36 b(h)433 b(step)f Fj(b)293 b Fl(+)g(1)800 30180 y(letters)552 b(from)g(eac)-36 b(h)552 b(side\))f(w)-36 b(e)553 b(see)f(that)f([)p Fj(u)22658 30379 y Fg(1)23184 30180 y Fl(])571 b(=)f([)p Fj(u)26799 30379 y Fg(2)27325 30180 y Fl(])h(=)f Fk(\242)221 b(\242)g(\242)571 b Fl(=)f([)p Fj(u)34642 30379 y Fh(n)p Fi(\241)p Fg(1)36471 30180 y Fl(].)933 b(Since,)582 b(b)-36 b(y)551 b(assumption,)581 b Fj(w)52274 30379 y Fi(\244)800 31785 y Fl(con)-36 b(tains)411 b(arbitrarily)h(long)f(palindromes,)416 b(w)-36 b(e)411 b(can)g(tak)-36 b(e)411 b Fj(n)g Fl(in)g(\()p 0 1 0 0 TeXcolorcmyk(5.6)p (#equation.5.6) [[367 431 382 443] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))h(arbitrarily)f(large.)572 b(In)411 b(particular,)800 33390 y(the)427 b(\\holes")h(arising)g(in)f(the)g(construction)g(of)h Fj(w)25373 33589 y Fi(\244)26326 33390 y Fl(m)-36 b(ust)426 b(include)h(arbitrarily)h(long)g(strings)f(of)h(consec-)800 34995 y(utiv)-36 b(e)414 b(0's)h(or)g(consecutiv)-36 b(e)414 b(1's.)573 b(This)414 b(is)h(only)g(p)36 b(ossible)414 b(if)h Fj(w)405 b Fl(=)368 b(00)221 b Fk(\242)g(\242)g(\242)i Fl(0)415 b(or)f Fj(w)405 b Fl(=)368 b(11)221 b Fk(\242)g(\242)g(\242)j Fl(1.)572 b(Th)-36 b(us)413 b Fj(w)450 b Fl(is)415 b(a)800 36600 y(palindrome.)p 51860 36600 45 878 v 51905 35766 781 45 v 51905 36600 V 52684 36600 45 878 v Black 800 39312 a Fe(Remark.)p Black 569 w Fl(The)463 b(con)-36 b(v)g(erse)463 b(of)h(the)e(lemma)i(is)f(also)h(true)e(\(though)g(w)-36 b(e)464 b(will)g(not)f(need)f(this)h(fact)g(here\):)800 40917 y(If)434 b Fj(w)469 b Fl(is)434 b(a)g(palindrome,)g(then)e Fj(w)16937 41116 y Fi(\244)17896 40917 y Fl(con)-36 b(tains)434 b(arbitrarily)g(long)h(palindromes.)2751 43629 y(W)-108 b(e)374 b(are)h(no)-36 b(w)374 b(ready)h(to)f(state)h(and)e(pro)-36 b(v)g(e)375 b(our)f(main)g(result,)386 b(giving)376 b(us)e(a)g (necessary)h(and)f(su\261cien)-36 b(t)800 45234 y(condition)395 b(for)g(a)g(\257xed)g(p)36 b(oin)-36 b(t)395 b Fe(w)415 b Fl(to)395 b(con)-36 b(tain)395 b(palindromes)g(of)h(arbitrary)f (length.)565 b(F)-108 b(or)394 b(similar)i(sub)72 b(ject)800 46840 y(matter,)434 b(see)f(Hof,)i(Knill,)g(and)e(Simon)g([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.knill) [[259 295 265 307] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)p Black 800 49552 a Fe(Theorem)573 b(5.1.)p Black 587 w Fd(L)-66 b(et)523 b Fj(w)559 b Fd(b)-66 b(e)523 b(a)h(\257nite)e(wor)-66 b(d)525 b(with)e Fk(j)p Fj(w)36 b Fk(j)478 b Fl(=)g Fj(b)g Fk(\270)h Fl(2)p Fd(,)538 b(and)524 b Fj(w)36 b Fl(\(1\))478 b(=)g(0)p Fd(.)774 b(Then)524 b Fe(w)545 b Fd(c)-66 b(ontains)800 51157 y(arbitr)g(arily)463 b(long)i(p)-66 b(alindr)g(omes)464 b(if)g(and)h(only)f(if)g Fj(w)501 b Fd(is)464 b(a)i(quasi-p)-66 b(alindr)g(ome.)p Black 800 53869 a(Pr)g(o)g(of.)p Black 649 w Fl(Supp)36 b(ose)473 b(\257rst)g(that)g Fj(w)f Fk(2)437 b(Q)p Fl(.)698 b(Then)474 b(b)-36 b(y)473 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 474 w(5.3)p (#proposition.5.3) [[367 232 382 244] [1 1 1 [3 3]] [0 0 1]] pdfm Black 475 w(w)-36 b(e)474 b(ha)-36 b(v)g(e)473 b Fj(\301)40682 54068 y Fh(w)41437 53869 y Fl(\()p Fj(w)36 b Fl(\))436 b Fk(2)g(P)109 b Fl(,)485 b(and)473 b(hence)800 55474 y Fj(\301)1570 54992 y Fg(2)p Fh(n)p Fg(+1)1570 55802 y Fh(w)3869 55474 y Fl(\()p Fj(w)36 b Fl(\))368 b Fk(2)h(P)542 b Fl(for)434 b(all)h Fj(n)p Fl(.)579 b(Th)-36 b(us)433 b Fj(\301)18511 54992 y Fi(1)18511 55802 y Fh(w)19507 55474 y Fl(\()p Fj(w)36 b Fl(\))368 b(=)g Fe(w)434 b Fl(con)-36 b(tains)434 b(arbitrarily)g(long)g(palindromes.)2751 57079 y(Con)-36 b(v)g(ersely)-108 b(,)391 b(if)379 b Fe(w)h Fl(con)-36 b(tains)378 b(arbitrarily)i(long)f(palindromes,)390 b(then)378 b(b)-36 b(y)379 b(Lemma)p 0 1 0 0 TeXcolorcmyk 378 w(5.1)p (#lemma.5.1) [[459 203 474 215] [1 1 1 [3 3]] [0 0 1]] pdfm Black 380 w(its)g(\257rst)f(di\256er-)800 58684 y(ence)351 b(\242)p Fe(w)g Fl(also)i(con)-36 b(tains)351 b(arbitrarily)h(long)g (palindromes.)550 b(If)352 b Fj(w)36 b Fl(\()p Fj(b)p Fl(\))368 b(=)h(0,)f(then)351 b(w)-36 b(e)351 b(can)g(apply)h(Theorem)p 0 1 0 0 TeXcolorcmyk 800 60289 a(4.1)p (#theorem.4.1) [[79 174 94 186] [1 1 1 [3 3]] [0 0 1]] pdfm Black 450 w(to)449 b(conclude)g(that)f(\(\242)p Fj(w)36 b Fl(\))15774 60488 y Fi(\244)16748 60289 y Fl(con)-36 b(tains)449 b(arbitrarily)h(long)f(palindromes.)625 b(By)449 b(Lemma)p 0 1 0 0 TeXcolorcmyk 449 w(5.2)p (#lemma.5.2) [[482 174 497 186] [1 1 1 [3 3]] [0 0 1]] pdfm Black 450 w(it)g(follo)-36 b(ws)800 61894 y(that)443 b(\242)p Fj(w)421 b Fk(2)385 b(P)109 b Fl(,)446 b(whic)-36 b(h)443 b(b)-36 b(y)443 b(Lemma)p 0 1 0 0 TeXcolorcmyk 443 w(5.1)p (#lemma.5.1) [[246 160 261 172] [1 1 1 [3 3]] [0 0 1]] pdfm Black 445 w(implies)g(that)g Fj(w)421 b Fk(2)385 b(Q)p Fl(.)608 b(If)444 b Fj(w)36 b Fl(\()p Fj(b)p Fl(\))384 b(=)i(1,)446 b(then)c(w)-36 b(e)444 b(cannot)f(apply)800 63499 y(Theorem)p 0 1 0 0 TeXcolorcmyk 451 w(4.1)p (#theorem.4.1) [[129 146 144 158] [1 1 1 [3 3]] [0 0 1]] pdfm Black 451 w(directly)451 b(to)g Fj(w)36 b Fl(.)629 b(Ho)-36 b(w)g(ev)g(er,)456 b(w)-36 b(e)451 b(ma)-36 b(y)451 b(apply)g(the)f (theorem)g(to)h(the)f(w)-36 b(ord)450 b Fj(u)398 b Fl(=)g Fj(\301)48462 63698 y Fh(w)49216 63499 y Fl(\()p Fj(w)36 b Fl(\))450 b(to)800 65104 y(obtain)f(\242)p Fe(w)395 b Fl(=)f(\242)p Fe(u)h Fl(=)f(\(\242)p Fj(u)p Fl(\))15377 65303 y Fi(\244)15903 65104 y Fl(.)623 b(It)449 b(follo)-36 b(ws)451 b(that)d(\(\242)p Fj(u)p Fl(\))28266 65303 y Fi(\244)29240 65104 y Fl(con)-36 b(tains)449 b(arbitrarily)g(long)g (palindromes.)624 b(As)800 66709 y(b)36 b(efore,)434 b(this)g(implies)g(that)f Fj(\301)15603 66908 y Fh(w)16357 66709 y Fl(\()p Fj(w)36 b Fl(\))368 b(=)h Fj(u)g Fk(2)f(Q)p Fl(.)579 b(By)434 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(5.3)p (#proposition.5.3) [[374 117 389 129] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(it)434 b(follo)-36 b(ws)436 b(that)d Fj(w)404 b Fk(2)369 b(Q)p Fl(.)p 51860 66709 V 51905 65876 781 45 v 51905 66709 V 52684 66709 45 878 v Black 26150 74617 a(10)p Black eop %%Page: 11 11 11 10 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(References)p Black 1450 4345 a Fl([1])p Black 652 w(Jean-P)-36 b(aul)636 b(Allouc)-36 b(he,)687 b(Andr)-36 b(\266)-614 b(e)636 b(Arnold,)687 b(Jean)636 b(Berstel,)688 b(Sre)-36 b(\267)-614 b(ck)-36 b(o)636 b(Brlek,)688 b(Simon)636 b(Plou\256e,)688 b(and)3474 5950 y(Bruce)553 b(E.)g(Sagan,)584 b(A)554 b(relativ)-36 b(e)554 b(of)g(the)f(Th)-36 b(ue-Morse)553 b(sequence,)584 b Fd(Discr)-66 b(ete)573 b(Math.)553 b Fe(139)h Fl(\(1995\),)3474 7555 y(455{461.)p Black 1450 10211 a([2])p Black 652 w(Jean-P)-36 b(aul)591 b(Allouc)-36 b(he)592 b(and)f(Roland)i(Bac)-36 b(her,)631 b(T)-108 b(o)36 b(eplitz)592 b(sequences,)632 b(pap)36 b(erfolding,)632 b(T)-108 b(o)-36 b(w)g(ers)592 b(of)3474 11816 y(Hanoi)434 b(and)f(progression-free)h(sequences)f(of)h(in)-36 b(tegers,)434 b Fd(Enseign.)464 b(Math.)432 b Fe(38)i Fl(\(1992\),)h(315{327.)p Black 1450 14472 a([3])p Black 652 w(Jean-P)-36 b(aul)440 b(Allouc)-36 b(he)442 b(and)e(Je\256rey)i(Shallit,)h(The)e(ubiquitous)g (Prouhet-Th)-36 b(ue-Morse)439 b(sequence,)3474 16077 y Fd(Se)-66 b(quenc)g(es)630 b(and)j(Their)f(Applic)-66 b(ations:)931 b(Pr)-66 b(o)g(c)g(e)g(e)g(dings)629 b(of)k(SET)-100 b(A)632 b('98)p Fl(,)662 b(Springer)615 b(Ser.)h(Discrete)3474 17682 y(Math.)433 b(Theor.)h(Comput.)g(Sci.,)g(Springer,)f(London,)g (1999,)i(pp.)e(1{16.)p Black 1450 20338 a([4])p Black 652 w(Jean-P)-36 b(aul)420 b(Allouc)-36 b(he)420 b(and)g(Je\256rey)g (Shallit,)p 0 1 0 0 TeXcolorcmyk 424 w(Sums)f(of)i(digits,)j(o)-36 b(v)g(erlaps,)424 b(and)419 b(palindromes)p [[306 534 519 546] [1 1 1 [3 3]] [0 0 1]] (http://dmtcs.loria.fr/volumes/abstracts/dm040101.abs.html) pdfm Black(,)k Fd(Dis-)3474 21943 y(cr)-66 b(ete)463 b(Math.)h(The)-66 b(or.)464 b(Comp.)h(Sci.)432 b Fe(4)h Fl(\(2000\),)i(1{10)g (\(electronic\).)p Black 1450 24599 a([5])p Black 652 w(Julien)542 b(Cassaigne)i(and)f(Juhani)f(Karh)-36 b(um\304)-650 b(aki,)570 b(T)-108 b(o)36 b(eplitz)544 b(w)-36 b(ords,)570 b(generalized)543 b(p)36 b(erio)g(dicit)-36 b(y)544 b(and)3474 26204 y(p)36 b(erio)g(dically)435 b(iterated)e(morphisms,)h Fd(Eur)-66 b(op)g(e)g(an)464 b(J.)g(Combin.)432 b Fe(18)i Fl(\(1997\),)h(497{510.)p Black 1450 28859 a([6])p Black 652 w(D.)550 b(Chalice,)581 b(Ho)-36 b(w)551 b(to)f(di\256eren)-36 b(tiate)550 b(and)f(in)-36 b(tegrate)551 b(sequences,)579 b Fd(A)-33 b(mer.)571 b(Math.)g(Monthly)666 b Fe(108)3474 30465 y Fl(\(2001\),)434 b(911{921.)p Black 1450 33120 a([7])p Black 652 w(Anna)412 b(E.)i(F)-108 b(rid,)417 b(Ov)-36 b(erlap-free)413 b(symmetric)g(D0L)h(w)-36 b(ords,)417 b Fd(Discr)-66 b(ete)445 b(Math.)h(The)-66 b(or.)445 b(Comput.)h(Sci.)3474 34725 y Fe(4)433 b Fl(\(2001\),)i(357{362.)p Black 1450 37381 a([8])p Black 652 w(A.)835 b(Hof,)935 b(O.)835 b(Knill,)936 b(and)834 b(B.)h(Simon,)934 b(Singular)835 b(con)-36 b(tin)g(uous)833 b(sp)36 b(ectrum)834 b(for)h(palindromic) 3474 38986 y(Sc)-36 b(hr\304)-650 b(odinger)432 b(op)36 b(erators,)434 b Fd(Comm.)464 b(Math.)g(Phys.)434 b Fe(174)g Fl(\(1995\),)h(149{159.)p Black 1450 41642 a([9])p Black 652 w(A.)452 b(Hoit,)458 b(The)453 b(distribution)e(of)i(generalized)g (sum-of-digits)f(functions,)457 b(Ph.D.)c(thesis,)k(Univ.)c(of)3474 43247 y(Illinois,)435 b(Urbana-Champaign,)e(1999.)p Black 800 45903 a([10])p Black 652 w(A.)h(Hoit,)g(Blo)36 b(c)-36 b(k)435 b(pro)36 b(ducts,)432 b(preprin)-36 b(t,)433 b(2002.)p Black 800 48559 a([11])p Black 652 w(K.)h(Jacobs,)g(Masc)-36 b(hinenerzeugte)433 b(0-1-folgen,)h Fd(Sele)-66 b(cta)464 b(Math.)433 b Fe(1)g Fl(\(1969\),)i(1{27.)p 800 51365 52000 45 v 800 53504 a(2000)g Fd(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Fl(:)577 b(Primary)434 b(11B85;)h(Secondary)e(68R15.)800 55109 y Fd(Keywor)-66 b(ds:)1151 b Fl(Th)-36 b(ue-Morse,)744 b(binary)682 b(sequence,)745 b(\257rst)682 b(di\256erence,)745 b(palindrome,)g(sk)-36 b(ew-palindrome,)800 56714 y(quasi-palindrome,)434 b(c)-36 b(hange)433 b(sequence,)h(cross)g(pro)36 b(duct,)433 b(blo)36 b(c)-36 b(k)434 b(pro)36 b(duct,)433 b(T)-108 b(o)36 b(eplitz)434 b(morphism.)p 800 58233 V 800 60445 a(\(Concerned)f(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A010060)p 16090 60657 4878 54 v [[217 173 261 185] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/ ~njas/sequences/eisA.cgi?Anum=A010060) pdfm Black 2 w(.\))p 800 62037 52000 45 v 800 64975 a(Receiv)-36 b(ed)647 b(Septem)-36 b(b)36 b(er)646 b(6)h(2002;)755 b(revised)647 b(v)-36 b(ersions)647 b(receiv)-36 b(ed)647 b(April)g(28)g(2003;)755 b(Decem)-36 b(b)36 b(er)646 b(2)h(2003.)800 66581 y(Published)433 b(in)g Fd(Journal)465 b(of)g(Inte)-66 b(ger)463 b(Se)-66 b(quenc)g(es)p Fl(,)431 b(Decem)-36 b(b)36 b(er)434 b(12)g(2003.)p 800 68099 V 800 70237 a(Return)f(to)p 0 1 0 0 TeXcolorcmyk 433 w(Journal)h(of)g(In)-36 b(teger)434 b(Sequences)f(home)g(page)p [[133 85 338 97] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black 26150 74617 a(11)p Black eop %%Trailer end end