%%Page: 1 1 1 0 bop Black 0 TeXcolorgray Black Black Black Black 10800 3607 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.3.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 5000 8918 a Fw(New)863 b(Lo)-72 b(w)g(er)862 b(Bound)f(On)g(The)g(Num)-72 b(b)72 b(er)862 b(of)11150 11253 y(T)-215 b(ernary)861 b(Square-F)-215 b(ree)861 b(W)-215 b(ords)23180 16284 y Fv(Xin)-43 b(yu)520 b(Sun)17160 18166 y(Departmen)-43 b(t)520 b(of)g(Mathematics)20553 20048 y(T)-130 b(emple)519 b(Univ)-43 b(ersit)g(y)18802 21930 y(Philadelphia,)518 b(P)-130 b(A)521 b(19122)25196 23811 y(USA)p 0 1 0 0 TeXcolorcmyk 18471 25693 a(xysun@math.temple.edu) p [[238 486 388 498] [1 1 1 [3 3]] [0 0 1]] (mailto:xysun@math.temple.edu) pdfm Black Black Black 23944 29299 a Fu(Abstract)2606 30849 y Ft(A)434 b(new)f(lo)-36 b(w)g(er)435 b(b)36 b(ound)432 b(on)i(the)f(n)-36 b(um)g(b)36 b(er)432 b(of)i Fs(n)p Ft(-letter)f(ternary)h(square-free)g(w)-36 b(ords)433 b(is)h(presen)-36 b(ted:)10314 32399 y(110)12264 31917 y Fr(n=)p Fq(42)14303 32399 y Ft(,)434 b(whic)-36 b(h)433 b(impro)-36 b(v)g(es)434 b(the)f(previous)h(b)36 b(est)433 b(result)g(of)h(65)40886 31917 y Fr(n=)p Fq(40)42925 32399 y Ft(.)21204 36090 y(1.)1153 b Fp(Intr)-30 b(oduction)2128 38414 y Ft(A)381 b(w)-36 b(ord)380 b Fs(w)416 b Ft(is)380 b(a)h(\257nite)f(sequence)g(of)h(letters)f(from)h(a)g(certain)f(alphab) 36 b(et)380 b(\247.)561 b(The)381 b(length)f(of)h(a)f(w)-36 b(ord)381 b(is)800 39964 y(the)357 b(n)-36 b(um)g(b)36 b(er)356 b(of)j(letters)e(of)i(the)e(w)-36 b(ord.)553 b(Binary)358 b(w)-36 b(ords)358 b(are)g(the)f(w)-36 b(ords)357 b(from)h(a)g(t)-36 b(w)g(o-letter)358 b(alphab)36 b(et)357 b Fo(f)p Ft(0,)800 41514 y(1)p Fo(g)p Ft(,)453 b(whereas)c(ternary)f(w) -36 b(ords)449 b(are)f(from)h(a)g(three-letter)e(alphab)36 b(et)449 b Fo(f)p Ft(0,)k(1,)f(2)p Fo(g)p Ft(.)624 b(A)449 b(w)-36 b(ord)448 b(is)h(square-free)800 43064 y(if)422 b(it)g(do)36 b(es)422 b(not)g(con)-36 b(tain)421 b(t)-36 b(w)g(o)422 b(iden)-36 b(tical)422 b(consecutiv)-36 b(e)422 b(sub)-36 b(w)g(ords)421 b(\(factors\),)k(i.e.,)g Fs(w)457 b Ft(cannot)422 b(b)36 b(e)421 b(written)800 44613 y(as)434 b Fs(axxb)g Ft(where)f Fs(a;)221 b(b;)g(x)435 b Ft(are)f(w)-36 b(ords)433 b(with)h Fs(x)f Ft(non-empt)-36 b(y)-108 b(.)2128 46163 y(It)575 b(is)g(easy)h(to)f(see)g(that)f(there)g(are)h(only)g (\257nitely)g(man)-36 b(y)575 b(binary)g(square-free)g(w)-36 b(ords.)1002 b(Ho)-36 b(w)g(ev)g(er,)800 47713 y(there)369 b(are)h(in\257nitely)g(man)-36 b(y)370 b(ternary)g(square-free)g(w)-36 b(ords.)557 b(The)370 b(fact)g(w)-36 b(as)370 b(pro)-36 b(v)g(ed)370 b(b)-36 b(y)369 b(utilizing)i(what)f(is)800 49263 y(no)-36 b(w)446 b(called)g(the)g(Prouhet-Th)-36 b(ue-Morse)443 b(sequence)j(\(see)g([)p 0 1 0 0 TeXcolorcmyk(10)p (#cite.LO) [[343 274 355 286] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]\).)615 b(Brinkh)-36 b(uis[)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.BR) [[424 274 430 286] [1 1 1 [3 3]] [0 0 1]] pdfm Black(],)449 b(Branden)-36 b(burg[)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.BG) [[510 274 516 286] [1 1 1 [3 3]] [0 0 1]] pdfm Black -1 w(])446 b(\(also)800 50812 y(in)473 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.BE) [[96 260 102 272] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]\),)483 b(Zeilb)36 b(erger[)p 0 1 0 0 TeXcolorcmyk(5)p (#cite.EZ) [[172 260 178 272] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])474 b(and)e(Grimm[)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.GR) [[248 260 254 272] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])i(sho)-36 b(w)g(ed)473 b(that)g(the)f(n)-36 b(um)g(b)36 b(ers)472 b(of)i(suc)-36 b(h)472 b(w)-36 b(ords)473 b(of)h(length)f Fs(n)h Ft(are)800 52401 y(greater)446 b(than)f(2)8917 51919 y Fr(n=)p Fq(24)10955 52401 y Ft(,)450 b(2)12416 51919 y Fr(n=)p Fq(21)14454 52401 y Ft(,)f(2)15914 51919 y Fr(n=)p Fq(17)17952 52401 y Ft(,)g(and)d(65)22604 51919 y Fr(n=)p Fq(40)25088 52401 y Ft(resp)36 b(ectiv)-36 b(ely)-108 b(.)616 b(Details)447 b(on)f(w)-36 b(ords)446 b(and)f(related)h(topics)800 53951 y(can)434 b(b)36 b(e)433 b(found)g(in)g([)p 0 1 0 0 TeXcolorcmyk(6)p (#cite.SF) [[166 231 172 243] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])h(and)f([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.WR) [[205 231 217 243] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)2128 55501 y(While)539 b(the)e(b)36 b(est)537 b(a)-36 b(v)-72 b(ailable)539 b(upp)36 b(er)536 b(b)36 b(ound)537 b(has)g(b)36 b(een)537 b(v)-36 b(ery)539 b(close)f(to)g(the) f(estimate)h(as)g(describ)36 b(ed)800 57051 y(later,)354 b(the)333 b(a)-36 b(v)-72 b(ailable)335 b(lo)-36 b(w)g(er)334 b(b)36 b(ounds)332 b(still)j(ha)-36 b(v)g(e)333 b(m)-36 b(uc)g(h)332 b(ro)36 b(om)334 b(for)g(impro)-36 b(v)g(emen)g(t.)545 b(Finding)333 b(b)36 b(etter)332 b(lo)-36 b(w)g(er)800 58600 y(b)36 b(ounds)436 b(has)i(p)36 b(osed)437 b(as)h(a)g (algorithmic)g(c)-36 b(hallenge,)440 b(as)d(w)-36 b(ell)439 b(as)f(a)g(theoretic)f(one.)590 b(As)438 b(explained)f(later,)800 60150 y(the)c(complexit)-36 b(y)435 b(of)f(the)f(algorithm)h(used)f (here)g(is)h(lik)-36 b(ely)436 b(\(v)-36 b(ery\))433 b(exp)36 b(onen)-36 b(tial.)19948 63841 y(2.)651 b Fp(Brinkhuis)502 b(Triples)2128 66166 y Ft(W)-108 b(e)472 b(denote)e Fs(a)p Ft(\()p Fs(n)p Ft(\))i(to)f(b)36 b(e)471 b(the)g(n)-36 b(um)g(b)36 b(er)470 b(of)i(ternary)f(square-free)g(w)-36 b(ords)472 b(of)g(length)f Fs(n)p Ft(.)692 b(It)471 b(is)h(easy)g(to) 800 67716 y(see)434 b(that)20658 69635 y Fs(a)p Ft(\()p Fs(m)294 b Ft(+)h Fs(n)p Ft(\))369 b Fo(\267)g Fs(a)p Ft(\()p Fs(m)p Ft(\))p Fs(a)p Ft(\()p Fs(n)p Ft(\))17183 b(\(2.1\))p Black 26544 70964 a Fn(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black 800 -3114 a Fn(2)p Black 800 -458 a Ft(for)434 b(all)h Fs(m;)655 b(n)369 b Fo(\270)g Ft(0,)434 b(whic)-36 b(h)434 b(implies)g(\(see)f(in)h([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.BE) [[282 721 288 733] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\))g(the)f(existence)h(of)g(the)f(limit)21902 1884 y Fs(s)368 b Ft(:=)692 b(lim)24625 2681 y Fr(n)p Fm(!1)27299 1884 y Fs(a)p Ft(\()p Fs(n)p Ft(\))29770 1336 y Fq(1)p Fr(=n)31337 1884 y Fs(;)18428 b Ft(\(2.2\))800 4534 y(whic)-36 b(h)433 b(is)h(also)h(called)f(the)f(gro)-36 b(wth)434 b(rate)f(or)h(\\connectiv)-36 b(e)434 b(constan)-36 b(t")434 b(of)g(ternary)f(square-free)h(w)-36 b(ords.)2128 6084 y(It)528 b(is)f(widely)i(b)36 b(eliev)-36 b(ed)527 b(that)g(the)g(a)-36 b(v)-72 b(ailable)529 b(upp)36 b(er)526 b(b)36 b(ounds)526 b(are)i(v)-36 b(ery)528 b(close)g(to)f(the)g(actual) h(v)-72 b(alue)800 7633 y(of)476 b Fs(s)p Ft(.)702 b(In)474 b(fact,)486 b(it)475 b(has)g(b)36 b(een)474 b(estimated)h(b)-36 b(y)475 b(No)36 b(onan)475 b(and)g(Zeilb)36 b(erger)475 b([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.NZ) [[407 648 413 660] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(that)e Fs(s)439 b Fo(\274)g Ft(1)p Fs(:)p Ft(302)477 b(using)e(the)800 9183 y(Zinn-Justin)504 b(metho)36 b(d,)524 b(and)506 b(they)g(ha)-36 b(v)g(e)506 b(also)h(pro)-36 b(v)g(ed)506 b(that)f Fs(s)492 b Fo(\267)h Ft(1)p Fs(:)p Ft(30201064)509 b(b)-36 b(y)506 b(implemen)-36 b(ting)506 b(the)800 10733 y(Golden-Jac)-36 b(kson)433 b(metho)36 b(d.)p Black 800 13140 a Fu(De\257nition)394 b(1.)p Black 484 w Ft(An)341 b Fs(n)p Ft(-Brinkh)-36 b(uis)341 b Fs(k)45 b Ft(-triple)341 b(is)h(three)f(sets)h(of)h(w)-36 b(ords)341 b Fo(B)383 b Ft(=)341 b Fo(fB)39027 12658 y Fq(0)39554 13140 y Ft(,)360 b Fo(B)41187 12658 y Fq(1)41714 13140 y Ft(,)g Fo(B)43347 12658 y Fq(2)43874 13140 y Fo(g)p Ft(,)h Fo(B)46172 12658 y Fr(i)46917 13140 y Ft(=)369 b Fo(f)p Fs(w)49928 12658 y Fr(i)49892 13468 y(j)50379 13140 y Fo(j)p Ft(1)g Fo(\267)800 14819 y Fs(j)444 b Fo(\267)369 b Fs(k)45 b Fo(g)p Ft(,)382 b(where)369 b Fs(w)9971 14337 y Fr(i)9935 15147 y(j)10791 14819 y Ft(are)g (square-free)h(w)-36 b(ords)369 b(of)h(length)e Fs(n)p Ft(,)383 b(suc)-36 b(h)368 b(that)h(for)h(an)-36 b(y)369 b(square-free)g(w)-36 b(ord)369 b Fs(i)49974 15018 y Fq(1)50500 14819 y Fs(i)50944 15018 y Fq(2)51469 14819 y Fs(i)51913 15018 y Fq(3)52439 14819 y Ft(,)800 16596 y(0)405 b Fo(\267)g Fs(i)3737 16795 y Fq(1)4262 16596 y Fs(;)221 b(i)5288 16795 y Fq(2)5814 16596 y Fs(;)g(i)6840 16795 y Fq(3)7771 16596 y Fo(\267)405 b Ft(2,)460 b(and)454 b(an)-36 b(y)455 b(1)404 b Fo(\267)h Fs(j)18738 16795 y Fq(1)19264 16596 y Fs(;)221 b(j)20384 16795 y Fq(2)20911 16596 y Fs(;)g(j)22031 16795 y Fq(3)22962 16596 y Fo(\267)404 b Fs(k)45 b Ft(,)460 b(the)454 b(w)-36 b(ord)455 b Fs(w)32405 16015 y Fr(i)32725 16138 y Fl(1)32369 16936 y Fr(j)32750 17059 y Fl(1)33265 16596 y Fs(w)34231 16015 y Fr(i)34551 16138 y Fl(2)34195 16936 y Fr(j)34576 17059 y Fl(2)35092 16596 y Fs(w)36058 16015 y Fr(i)36378 16138 y Fl(3)36022 16936 y Fr(j)36403 17059 y Fl(3)37374 16596 y Ft(of)g(length)f(3)p Fs(n)h Ft(is)g(also)g(square-)800 18146 y(free.)2128 20553 y(Based)544 b(on)g(an)g Fs(n)p Ft(-Brinkh)-36 b(uis)543 b Fs(k)45 b Ft(-triple,)572 b(w)-36 b(e)544 b(can)g(de\257ne)f(the)g (follo)-36 b(wing)546 b(set)e(of)h(uniformly)f(gro)-36 b(wing)800 22102 y(morphisms:)18430 27211 y Fs(\275)369 b Ft(=)20851 24090 y Fk(8)20851 25285 y(>)20851 25684 y(<)20851 28075 y(>)20851 28473 y(:)22585 24992 y Ft(0)g Fo(!)h Fs(w)26268 24510 y Fq(0)26232 25320 y Fr(j)26613 25443 y Fl(0)27128 24992 y Fs(;)656 b Ft(1)369 b Fo(\267)g Fs(j)31104 25191 y Fq(0)31999 24992 y Fo(\267)g Fs(k)45 b Ft(;)22585 27171 y(1)369 b Fo(!)h Fs(w)26268 26689 y Fq(1)26232 27500 y Fr(j)26613 27623 y Fl(1)27128 27171 y Fs(;)656 b Ft(1)369 b Fo(\267)g Fs(j)31104 27370 y Fq(1)31999 27171 y Fo(\267)g Fs(k)45 b Ft(;)22585 29351 y(2)369 b Fo(!)h Fs(w)26268 28869 y Fq(2)26232 29679 y Fr(j)26613 29802 y Fl(2)27128 29351 y Fs(;)656 b Ft(1)369 b Fo(\267)g Fs(j)31104 29550 y Fq(2)31999 29351 y Fo(\267)g Fs(k)45 b(:)50126 27211 y Ft(\(2.3\))2128 31374 y(As)445 b(pro)-36 b(v)g(en)445 b(in)f([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.BG) [[164 435 170 447] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(],)k([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.CR) [[183 435 189 447] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])d(and)g([)p 0 1 0 0 TeXcolorcmyk(9)p (#cite.LE) [[223 435 228 447] [1 1 1 [3 3]] [0 0 1]] pdfm Black(],)j Fs(\275)d Ft(are)g(square-free)g(morphisms,)i(i.e.,)i(they)c (map)f(eac)-36 b(h)445 b(square-free)800 32924 y(w)-36 b(ord)434 b(of)g(length)f Fs(m)g Ft(on)-36 b(to)434 b Fs(k)14690 32442 y Fr(m)16011 32924 y Ft(di\256eren)-36 b(t)433 b(images)h(of)g(square-free)g(w)-36 b(ords)434 b(of)g(length)f Fs(nm)p Ft(.)2128 34473 y(Therefore,)i(the)e(existence) h(of)g(an)g Fs(n)p Ft(-Brinkh)-36 b(uis)433 b Fs(k)45 b Ft(-triple)433 b(indicates)h(that)23306 36525 y Fs(a)p Ft(\()p Fs(mn)p Ft(\))p 23306 37118 3609 54 v 23694 38335 a Fs(a)p Ft(\()p Fs(m)p Ft(\))27416 37424 y Fo(\270)369 b Fs(k)29539 36875 y Fr(m)50126 37424 y Ft(\(2.4\))800 40387 y(for)434 b(an)-36 b(y)434 b Fs(m)369 b Fo(\270)g Ft(1,)434 b(whic)-36 b(h)433 b(implies)18112 43682 y Fs(s)18725 43134 y Fr(n)p Fm(\241)p Fq(1)20922 43682 y Ft(=)692 b(lim)22302 44479 y Fr(n)p Fm(!1)24977 41809 y Fk(\265)26087 42783 y Fs(a)p Ft(\()p Fs(mn)p Ft(\))p 26087 43377 V 26475 44593 a Fs(a)p Ft(\()p Fs(m)p Ft(\))29829 41809 y Fk(\266)30806 42107 y Fq(1)p Fr(=m)33004 43682 y Fo(\270)369 b Fs(k)45 b(;)14638 b Ft(\(2.5\))800 46888 y(and)433 b(th)-36 b(us)433 b(yields)h(the)f(lo)-36 b(w)g(er)434 b(b)36 b(ound)432 b(of)j Fs(s)368 b Fo(\270)i Fs(k)24080 46406 y Fq(1)p Fr(=)p Fq(\()p Fr(n)p Fm(\241)p Fq(1\))27581 46888 y Ft(.)2128 48437 y(Giv)-36 b(en)434 b(the)f(p)36 b(erm)-36 b(utation)433 b Fs(\277)581 b Ft(=)433 b(\(0,)h(1,)h(2\),)f (w)-36 b(e)434 b(can)f(ha)-36 b(v)g(e)p Black 800 50844 a Fu(De\257nition)415 b(2.)p Black 497 w Ft(A)360 b(quasi-sp)36 b(ecial)360 b Fs(n)p Ft(-Brinkh)-36 b(uis)360 b Fs(k)45 b Ft(-triple)359 b(is)h(an)f Fs(n)p Ft(-Brinkh)-36 b(uis)360 b Fs(k)45 b Ft(-triple)359 b(suc)-36 b(h)359 b(that)g Fo(B)50893 50362 y Fq(1)51788 50844 y Ft(=)800 52394 y Fs(\277)148 b Ft(\()p Fo(B)2931 51912 y Fq(0)3458 52394 y Ft(\),)433 b Fo(B)5670 51912 y Fq(2)6566 52394 y Ft(=)369 b Fs(\277)148 b Ft(\()p Fo(B)10078 51912 y Fq(1)10604 52394 y Ft(\).)p Black 800 54801 a Fu(De\257nition)390 b(3.)p Black 480 w Ft(A)338 b(sp)36 b(ecial)339 b Fs(n)p Ft(-Brinkh)-36 b(uis)337 b Fs(k)45 b Ft(-triple)338 b(is)g(a)g (quasi-sp)36 b(ecial)339 b Fs(n)p Ft(-Brinkh)-36 b(uis)338 b Fs(k)45 b Ft(-triple)337 b(suc)-36 b(h)337 b(that)800 56351 y Fs(w)405 b Fo(2)368 b(B)4301 55869 y Fq(0)5261 56351 y Ft(implies)p 9676 55619 966 54 v 434 w Fs(w)405 b Fo(2)368 b(B)13177 55869 y Fq(0)13704 56351 y Ft(,)434 b(where)p 18256 55619 V 433 w Fs(w)469 b Ft(is)434 b(the)f(rev)-36 b(ersion)434 b(of)h Fs(w)36 b Ft(.)2128 58758 y(Grimm[)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.GR) [[131 188 137 200] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])425 b(w)-36 b(as)426 b(able)f(to)g(construct)f(a)h(sp)36 b(ecial)425 b(41-Brinkh)-36 b(uis)425 b(65-triple,)i(hence)d(pro)-36 b(v)g(ed)424 b Fs(s)369 b Fo(\270)g Ft(65)50501 58276 y Fq(1)p Fr(=)p Fq(40)52439 58758 y Ft(.)21439 61804 y(3.)651 b Fp(Main)502 b(Resul)-89 b(ts)p Black 800 64129 a Fu(De\257nition)409 b(4.)p Black 493 w Ft(A)354 b(w)-36 b(ord)354 b Fs(w)390 b Ft(is)355 b(admissible)f(if)h(\()p Fs(w)36 b(;)221 b(\277)148 b Ft(\()p Fs(w)36 b Ft(\))p Fs(;)221 b(\277)29727 63647 y Fq(2)30253 64129 y Ft(\()p Fs(w)36 b Ft(\)\))354 b(is)g(a)h(quasi-sp)36 b(ecial)355 b(Brinkh)-36 b(uis)354 b(1-triple)800 65679 y(b)-36 b(y)434 b(itself.)p Black 800 68086 a Fu(De\257nition)398 b(5.)p Black 486 w Ft(An)344 b(optimal)h(quasi-sp)36 b(ecial)346 b(\(sp)36 b(ecial\))346 b Fs(n)p Ft(-Brinkh)-36 b(uis)344 b Fs(k)45 b Ft(-triple)345 b(is)g(a)g(quasi-sp)36 b(ecial)346 b(\(sp)36 b(e-)800 69635 y(cial\))368 b Fs(n)p Ft(-Brinkh)-36 b(uis)367 b Fs(k)45 b Ft(-triple)368 b(suc)-36 b(h)366 b(that)h(an)-36 b(y)368 b(quasi-sp)36 b(ecial)369 b(\(sp)36 b(ecial\))368 b Fs(n)p Ft(-Brinkh)-36 b(uis)367 b Fs(l)29 b Ft(-triple)367 b(has)h Fs(l)399 b Fo(\267)369 b Fs(k)45 b(:)p Black Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black 52288 -3114 a Fn(3)p Black 2128 -458 a Ft(T)-108 b(o)497 b(\257nd)e(the)h(optimal)h (quasi-sp)36 b(ecial)497 b Fs(n)p Ft(-Brinkh)-36 b(uis)496 b(triples,)513 b(w)-36 b(e)496 b(only)h(need)f(to)h(\257nd)e(the)h(set) g(of)h(all)800 1092 y(admissible)417 b(w)-36 b(ords)417 b(of)g(length)f Fs(n)p Ft(,)421 b(and)416 b(its)h(largest)g(subset)f (in)g(whic)-36 b(h)417 b(an)-36 b(y)417 b(three)f(w)-36 b(ords)416 b Fs(w)45830 1291 y Fq(1)46356 1092 y Fs(;)221 b(w)47868 1291 y Fq(2)48394 1092 y Fs(;)g(w)49906 1291 y Fq(3)50849 1092 y Ft(can)800 2642 y(form)340 b(a)f(quasi-sp)36 b(ecial)341 b Fs(n)p Ft(-Brinkh)-36 b(uis)339 b(3-triple,)358 b(i.e.,)h Fo(ff)p Fs(w)28781 2841 y Fq(1)29307 2642 y Ft(,)f Fs(w)30956 2841 y Fq(2)31482 2642 y Ft(,)g Fs(w)33131 2841 y Fq(3)33657 2642 y Fo(g)p Ft(,)h Fo(f)p Fs(\277)148 b Ft(\()p Fs(w)37854 2841 y Fq(1)38379 2642 y Ft(\),)359 b Fs(\277)148 b Ft(\()p Fs(w)41754 2841 y Fq(2)42279 2642 y Ft(\),)358 b Fs(\277)148 b Ft(\()p Fs(w)45653 2841 y Fq(3)46179 2642 y Ft(\))p Fo(g)p Ft(,)358 b Fo(f)p Fs(\277)49445 2160 y Fq(2)49972 2642 y Ft(\()p Fs(w)51408 2841 y Fq(1)51933 2642 y Ft(\),)800 4192 y Fs(\277)1513 3709 y Fq(2)2039 4192 y Ft(\()p Fs(w)3475 4391 y Fq(2)4000 4192 y Ft(\),)562 b Fs(\277)6142 3709 y Fq(2)6668 4192 y Ft(\()p Fs(w)8104 4391 y Fq(3)8630 4192 y Ft(\))p Fo(gg)536 b Ft(is)g(a)g(quasi-sp)36 b(ecial)537 b Fs(n)p Ft(-Brinkh)-36 b(uis)536 b(3-triple.)885 b(A)536 b(Maple)g(pac)-36 b(k)-72 b(age)537 b(w)-36 b(as)536 b(written)g(to)800 5741 y(calculate)434 b(suc)-36 b(h)433 b(w)-36 b(ords)434 b(and)f(sets.)578 b(The)434 b(results)f(are)h(listed)f(b)36 b(elo)-36 b(w.)p Black 800 8749 a Fu(Prop)42 b(osition)618 b(3.1.)p Black 606 w Fj(Sp)-66 b(e)g(cial)557 b Fs(n)p Fj(-Brinkhuis)j(triples)e (yield)h(the)g(b)-66 b(est)558 b(p)-66 b(ossible)559 b(r)-66 b(esults)559 b(for)g(e)-66 b(ach)559 b Ft(13)544 b Fo(\267)800 10298 y Fs(n)369 b Fo(\267)h Ft(20)p Fj(,)379 b(and)358 b(quasi-sp)-66 b(e)g(cial)357 b(Brinkhuis)h(triples)f(do)i (not)e(yield)h(b)-66 b(etter)356 b(r)-66 b(esults)358 b(than)g(sp)-66 b(e)g(cial)357 b Fs(n)p Fj(-Brinkhuis)800 11848 y(triples)465 b(for)f(e)-66 b(ach)465 b Ft(13)369 b Fo(\267)g Fs(n)h Fo(\267)f Ft(39)p Fj(,)465 b(exc)-66 b(ept)463 b(37.)p Black Black 10242 13719 33117 45 v 11320 14804 a Fs(n)6436 b(b)19085 15003 y Fq(1)25923 14804 y Fs(k)26599 15003 y Fq(1)33561 14804 y Fs(b)34114 15003 y Fq(2)41602 14804 y Fs(k)42278 15003 y Fq(2)p 10242 15313 V 10795 16398 a Ft(13)6865 b(1)g(1)f(1)7515 b(1)10795 17947 y(14)6865 b(0)g(0)f(0)7515 b(0)10795 19497 y(15)6865 b(0)g(0)f(0)7515 b(0)10795 21047 y(16)6865 b(0)g(0)f(0)7515 b(0)10795 22597 y(17)6865 b(1)g(1)f(1)7515 b(1)10795 24146 y(18)6865 b(1)g(2)f(1)7515 b(2)10795 25696 y(19)6865 b(1)g(1)f(1)7515 b(1)10795 27246 y(20)6865 b(0)g(0)f(0)7515 b(0)10795 28796 y(21)6865 b(0)g(0)f(0)7515 b(0)10795 30345 y(22)6865 b(0)g(0)f(0)7515 b(0)10795 31895 y(23)6865 b(1)g(3)f(1)7515 b(3)10795 33445 y(24)6865 b(5)g(2)f(3)7515 b(2)10795 34995 y(25)6865 b(1)g(5)f(1)7515 b(5)10795 36544 y(26)6865 b(2)g(2)f(2)7515 b(2)10795 38094 y(27)6865 b(1)g(3)f(1)7515 b(3)10795 39644 y(28)6865 b(4)g(4)f(2)7515 b(4)10795 41194 y(29)6865 b(2)g(6)f(2)7515 b(6)10795 42743 y(30)6865 b(1)g(8)f(1)7515 b(8)10795 44293 y(31)6865 b(4)g(7)f(2)7515 b(7)10795 45843 y(32)6865 b(1)g(8)f(1)7515 b(8)10795 47393 y(33)6865 b(1)6215 b(12)6864 b(1)h(12)10795 48942 y(34)6215 b(33)g(10)6864 b(5)h(10)10795 50492 y(35)g(2)6215 b(18)6864 b(2)h(18)10795 52042 y(36)g(1)6215 b(32)6864 b(1)h(32)10795 53592 y(37)6215 b(66)g(32)f(24)6865 b(31)10795 55141 y(38)g(9)6215 b(28)6864 b(3)h(28)10795 56691 y(39)g(1)6215 b(32)6864 b(1)h(32)10795 58241 y(40)21894 b(2)6865 b(48)10795 59791 y(41)21894 b(8)6865 b(65)10795 61340 y(42)21894 b(4)6865 b(76)10795 62890 y(43)21894 b(2)6215 b(110)p 10242 63399 V 2128 66536 a(In)403 b(the)f(table)h(ab) 36 b(o)-36 b(v)g(e,)410 b Fs(n)403 b Ft(is)g(the)g(length)f(of)i(the)e (w)-36 b(ords;)414 b Fs(b)30067 66735 y Fq(1)30995 66536 y Ft(and)402 b Fs(k)34169 66735 y Fq(1)35099 66536 y Ft(are)h(the)f(n)-36 b(um)g(b)36 b(ers)401 b(of)j(all)f(a)-36 b(v)-72 b(ailable)800 68086 y(optimal)403 b(quasi-sp)36 b(ecial)404 b(Brinkh)-36 b(uis)402 b(triples)g(and)g(the)g(n)-36 b(um)g(b)36 b(ers)401 b(of)i(elemen)-36 b(ts)402 b(in)h(the)e(triples;) 414 b Fs(b)48172 68285 y Fq(2)49100 68086 y Ft(and)402 b Fs(k)52274 68285 y Fq(2)800 69635 y Ft(are)470 b(those)g(of)h(the)f (sp)36 b(ecial)471 b(Brinkh)-36 b(uis)469 b(triples.)688 b(Notice)471 b(the)e(n)-36 b(um)g(b)36 b(ers)469 b(of)i(the)e(triples)h (and)g(their)g(sizes)p Black Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black 800 -3114 a Fn(4)p Black 800 -458 a Ft(do)370 b(not)f(alw)-36 b(a)g(ys)371 b(gro)-36 b(w)370 b(as)g Fs(n)g Ft(do)36 b(es,)383 b(and)369 b(o)36 b(ccasionally)372 b(there)d(are)h(extraordinary)g(amoun)-36 b(t)369 b(of)h(the)f(triples)800 1092 y(for)434 b(certain)g(w)-36 b(ord)433 b(lengths,)h(i.e.,)h(34)f(and)f(37.)2128 2642 y(Although)458 b(there)f(are)h(often)g(more)f(c)-36 b(hoices)458 b(for)h(the)e(regular)h(and)f(quasi-sp)36 b(ecial)459 b(Brinkh)-36 b(uis)457 b(triples)800 4192 y(than)522 b(the)h(sp)36 b(ecial)524 b(Brinkh)-36 b(uis)522 b(triples)h(as)h (listed)f(ab)36 b(o)-36 b(v)g(e,)546 b(none)523 b(of)h(them)e(can)h(b) 36 b(e)523 b(com)-36 b(bined)522 b(to)i(form)800 5741 y(larger)472 b(triples.)691 b(And)470 b(the)h(exception)h(of)f Fs(n)434 b Ft(=)f(37)471 b(has)h(hardly)f(an)-36 b(y)471 b(signi\257cance)h(b)36 b(ecause)471 b(the)f(results)800 7291 y(are)500 b(sup)36 b(erceded)499 b(b)-36 b(y)500 b(the)g(36-Brinkh)-36 b(uis)500 b(32-triples)g(already)-108 b(.)779 b(These)500 b(results)g(strongly)h(suggest)f(that)800 8841 y(the)433 b(sp)36 b(ecial)434 b(Brinkh)-36 b(uis)434 b(triples)f(will)i(generally)g(yield)f(the)f(b)36 b(est)433 b(results)g(regardless)h(of)h Fs(n)p Ft(.)2128 10390 y(It)504 b(is)g(reasonable)f(to)h(b)36 b(eliev)-36 b(e)504 b(that)f(there)g(exist)h Fs(n)p Ft(-Brinkh)-36 b(uis)503 b(triples)g(that)g(are)h(not)f(quasi-sp)36 b(ecial)800 11940 y(when)328 b Fs(n)369 b(>)g Ft(20,)350 b(or)328 b(quasi-sp)36 b(ecial)329 b Fs(n)p Ft(-Brinkh)-36 b(uis)327 b(triples)h(that)g(are)g(not)g(sp)36 b(ecial)329 b(when)e Fs(n)370 b(>)e Ft(39.)544 b(Ho)-36 b(w)g(ev)g(er,)800 13490 y(as)396 b(explained)g(in)f(the)g(pro)36 b(of)396 b(of)g(the)f(follo)-36 b(wing)397 b(prop)36 b(osition,)404 b(it)395 b(is)h(v)-72 b(ary)396 b(hard)f(to)h(\257nd)e(suc)-36 b(h)394 b(triples)i(due)800 15040 y(to)434 b(the)f(complexit)-36 b(y)-108 b(.)p Black 800 23530 a Fu(Prop)42 b(osition)334 b(3.2.)p Black 443 w Fj(The)e(fol)66 b(lowing)332 b(43-Brinkhuis)g (110-triple)g(exists,)357 b(and)332 b(thus)h(shows)h Fs(s)368 b Fo(\270)i Ft(110)49561 23048 y Fq(1)p Fr(=)p Fq(42)51868 23530 y Ft(=)800 25080 y(1)p Fs(:)p Ft(118419)221 b Fs(:)g(:)g(:)374 b(>)368 b Ft(65)10511 24597 y Fq(1)p Fr(=)p Fq(40)12818 25080 y Ft(=)h(1)p Fs(:)p Ft(109999)221 b Fs(:)g(:)g(:)t Fj(:)p Black Black 10882 31976 a Fo(f)1107 b Fj(0120212012102120102012102010212012102120210,)12653 33526 y(0120212010210120102012102010210120102120210,)12653 35076 y(0120212010201210212021020120212012102120210,)12653 36626 y(0120212012102120210201202120121020102120210,)12653 38175 y(0120210201210120210121020120212012102120210,)12653 39725 y(0120212012102120210201210120210121020120210,)12653 41275 y(0120210201210120102120210120212012102120210,)12653 42825 y(0120212012102120210120212010210121020120210,)12653 44374 y(0120210201210120212010210120212012102120210,)12653 45924 y(0120212012102120210120102120210121020120210,)12653 47474 y(0120212010201210212010210120212012102120210,)12653 49024 y(0120212012102120210120102120121020102120210,)12653 50573 y(0120212010210121021201210120212012102120210,)12653 52123 y(0120212012102120210121021201210120102120210,)12653 53673 y(0120212012101201021201210120212012102120210,)12653 55223 y(0120212012102120210121021201021012102120210,)12653 56772 y(0120212010210121021202102010212012102120210,)12653 58322 y(0120212012102120102012021201210120102120210,)12653 59872 y(0120212012101201021202102010212012102120210,)12653 61422 y(0120212012102120102012021201021012102120210,)12653 62971 y(0120212010210120102012102010212012102120210,)12653 64521 y(0120212012102120102012102010210120102120210,)12653 66071 y(0120210201210120102012102010212012102120210,)12653 67621 y(0120212012102120102012102010210121020120210,)12653 69170 y(0120210201210120212012102010212012102120210,)p Black Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black 52288 -3114 a Fn(5)p Black Black Black 12321 -480 a Fj (0120212012102120102012102120210121020120210,)12321 1070 y(0120212010201210212012102010212012102120210,)12321 2620 y(0120212012102120102012102120121020102120210,)12321 4169 y(0120210201210212021012102010212012102120210,)12321 5719 y(0120212012102120102012101202120121020120210,)12321 7269 y(0120212012101201021012102010212012102120210,)12321 8819 y(0120212012102120102012101201021012102120210,)12321 10368 y(0120212010201210201021012010212012102120210,)12321 11918 y(0120212012102120102101201020121020102120210,)12321 13468 y(0120212010212021020121012010212012102120210,)12321 15018 y(0120212012102120102101210201202120102120210,)12321 16567 y(0120212010210121020121012010212012102120210,)12321 18117 y(0120212012102120102101210201210120102120210,)12321 19667 y(0120212012101201021202102012021012102120210,)12321 21217 y(0120212012101202102012021201021012102120210,)12321 22766 y(0120210201210120212012102012021012102120210,)12321 24316 y(0120212012101202102012102120210121020120210,)12321 25866 y(0120212010201210212012102012021012102120210,)12321 27416 y(0120212012101202102012102120121020102120210,)12321 28965 y(0120212010210120102120121012021012102120210,)12321 30515 y(0120212012101202101210212010210120102120210,)12321 32065 y(0120210201210120102120121012021012102120210,)12321 33614 y(0120212012101202101210212010210121020120210,)12321 35164 y(0120212010210120102120210201021012102120210,)12321 36714 y(0120212012101201020120212010210120102120210,)12321 38264 y(0120210201210120102120210201021012102120210,)12321 39813 y(0120212012101201020120212010210121020120210,)12321 41363 y(0120212010210121021201210201021012102120210,)12321 42913 y(0120212012101201020121021201210120102120210,)12321 44463 y(0120212010210120102012021201021012102120210,)12321 46012 y(0120212012101201021202102010210120102120210,)12321 47562 y(0120210201210120102012021201021012102120210,)12321 49112 y(0120212012101201021202102010210121020120210,)12321 50662 y(0120210201210212021012021201021012102120210,)12321 52211 y(0120212012101201021202101202120121020120210,)12321 53761 y(0120210201210120210121021201021012102120210,)12321 55311 y(0120212012101201021201210120210121020120210,)12321 56861 y(0120212010210120102012101201021012102120210,)12321 58410 y(0120212012101201021012102010210120102120210,)12321 59960 y(0120210201210120212012101201021012102120210,)12321 61510 y(0120212012101201021012102120210121020120210,)12321 63060 y(0120212010201210212012101201021012102120210,)p Black Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black 800 -3114 a Fn(6)p Black Black Black 11989 -480 a Fj (0120212012101201021012102120121020102120210,)11989 1070 y(0120210201210120212012102012021020102120210,)11989 2620 y(0120212010201202102012102120210121020120210,)11989 4169 y(0120212010201210212012102012021020102120210,)11989 5719 y(0120212010201202102012102120121020102120210,)11989 7269 y(0120212010210120102120121012021020102120210,)11989 8819 y(0120212010201202101210212010210120102120210,)11989 10368 y(0120210201210120102120121012021020102120210,)11989 11918 y(0120212010201202101210212010210121020120210,)11989 13468 y(0120210201210212012101201020121020102120210,)11989 15018 y(0120212010201210201021012102120121020120210,)11989 16567 y(0120210201210212012101202120121020102120210,)11989 18117 y(0120212010201210212021012102120121020120210,)11989 19667 y(0120212010210120102012102120121020102120210,)11989 21217 y(0120212010201210212012102010210120102120210,)11989 22766 y(0120210201210212021012102120121020102120210,)11989 24316 y(0120212010201210212012101202120121020120210,)11989 25866 y(0120210201210212021020102120121020102120210,)11989 27416 y(0120212010201210212010201202120121020120210,)11989 28965 y(0120212010201210120102120210121020102120210,)11989 30515 y(0120212010201210120212010210121020102120210,)11989 32065 y(0120210201210212021020120210121020102120210,)11989 33614 y(0120212010201210120210201202120121020120210,)11989 35164 y(0120212010210120102120210201202120102120210,)11989 36714 y(0120212010212021020120212010210120102120210,)11989 38264 y(0120210201210120102120210201202120102120210,)11989 39813 y(0120212010212021020120212010210121020120210,)11989 41363 y(0120212010210121021201210201202120102120210,)11989 42913 y(0120212010212021020121021201210120102120210,)11989 44463 y(0120212010210121021202102010210120102120210,)11989 46012 y(0120212010210120102012021201210120102120210,)11989 47562 y(0120210201210120102012102010210120102120210,)11989 49112 y(0120212010210120102012102010210121020120210,)11989 50662 y(0120210201210120212012102010210120102120210,)11989 52211 y(0120212010210120102012102120210121020120210,)11989 53761 y(0120210201210212021012102010210120102120210,)11989 55311 y(0120212010210120102012101202120121020120210,)11989 56861 y(0120210201210120102012021201210120102120210,)11989 58410 y(0120212010210121021202102010210121020120210,)11989 59960 y(0120210201210212021012021201210120102120210,)11989 61510 y(0120212010210121021202101202120121020120210,)11989 63060 y(0120210201210120210121021201210120102120210,)11989 64609 y(0120212010210121021201210120210121020120210)1513 b Fo(g)800 68086 y Fu(Pro)42 b(of:)533 b Ft(Eac)-36 b(h)344 b(admissible)g(w)-36 b(ord)344 b(is)g(of)h(length)f(at)g(least)g(13)h (and)e(of)i(the)f(form)g(either)g(012021)221 b Fo(\242)g(\242)g(\242)j Ft(120210)800 69635 y(or)513 b(012102)221 b Fo(\242)g(\242)g(\242)j Ft(201210)514 b(as)f(pro)-36 b(v)g(ed)512 b(b)-36 b(y)512 b(Grimm)g([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.GR) [[302 90 308 102] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)815 b(So)512 b(w)-36 b(e)513 b(\257rst)e(\257nd)g(all)j (the)d(square-free)i(w)-36 b(ords)512 b(of)p Black Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black 52288 -3114 a Fn(7)p Black 800 -458 a Ft(length)480 b Fs(n)328 b Fo(\241)f Ft(12,)494 b(attac)-36 b(h)480 b(the)g(t)-36 b(w)g(o)481 b(pairs)f(of)i(pre\257xes)e(and)g(su\261xes)h(to)f(these)h(w)-36 b(ords,)492 b(then)480 b(determine)800 1092 y(if)428 b(the)e(results)g(are)h(square-free)g(and)g(admissible)g(w)-36 b(ords,)428 b(and)f(lab)36 b(el)427 b(them)f(from)h(1)g(to)g Fs(m)p Ft(,)i(where)d Fs(m)h Ft(is)800 2642 y(the)383 b(total)h(n)-36 b(um)g(b)36 b(er)382 b(of)j(suc)-36 b(h)382 b(w)-36 b(ords.)562 b(The)384 b(next)f(step)g(is)h(to)g(\257nd)e(all)j (quasi-sp)36 b(ecial)384 b(\(sp)36 b(ecial\))384 b(Brinkh)-36 b(uis)800 4192 y(3-triples)484 b(and)g(replace)g(the)g(w)-36 b(ords)484 b(with)h(the)f(lab)36 b(els)485 b(w)-36 b(e)484 b(just)g(assigned)h(to)f(them.)730 b(Th)-36 b(us)484 b(eac)-36 b(h)484 b(triple)800 5741 y(corresp)36 b(ond)454 b(to)h(a)g(unique)f(ordered)g(list)h(of)g(three)f(di\256eren)-36 b(t)454 b(in)-36 b(tegers,)460 b(and)454 b(w)-36 b(e)455 b(ha)-36 b(v)g(e)454 b(created)h(a)g(set)f(of)800 7291 y(lists)481 b(of)g(in)-36 b(tegers)480 b Fs(S)77 b Ft(.)719 b(Note)480 b(that)g(if)h(the)f(square-free)h(w)-36 b(ords)480 b(of)h(length)f Fs(n)327 b Fo(\241)h Ft(12)481 b(are)f(kno)-36 b(wn,)493 b(the)479 b(rest)800 8841 y(of)540 b(the)f(pro)36 b(cess)539 b(ab)36 b(o)-36 b(v)g(e)540 b(only)f(tak)-36 b(e)540 b(p)36 b(olynomial)541 b(time.)895 b(No)-36 b(w)540 b(the)e(problem)h(is)g(reduced)f(to)i(\257nd)e(the)800 10390 y(largest)412 b(subset)f Fs(T)593 b Ft(of)412 b Fo(f)p Ft(1)p Fs(;)221 b(:)g(:)g(:)k(;)c(m)p Fo(g)412 b Ft(so)g(that)f(the)g(list)h(of)h(an)-36 b(y)412 b(three)f(elemen)-36 b(ts)411 b(of)h Fs(T)593 b Ft(is)412 b(an)g(elemen)-36 b(t)411 b(of)i Fs(S)77 b Ft(.)800 11940 y(Suc)-36 b(h)479 b(a)h(question)g(is)g(ob)-36 b(viously)482 b(NP)-108 b(,)479 b(b)36 b(ecause)480 b(the)g(certi\257cate)g(will)h(b)36 b(e)480 b(the)f(solution)h(itself,)493 b(and)480 b(the)800 13490 y(time)472 b(required)g(to)g(v)-36 b(erify)474 b(the)e(certi\257cate)g(will)h(b)36 b(e)472 b Fs(O)36 b Ft(\()28369 12414 y Fk(\241)28978 12901 y Fr(n)29028 13948 y Fq(3)29549 12414 y Fk(\242)30158 13490 y Ft(\),)481 b(th)-36 b(us)471 b(p)36 b(olynomial.)696 b(F)-108 b(ortunately)g(,)481 b(w)-36 b(e)473 b(are)800 15040 y(not)433 b(obliged)h(to)g(tell)g(ho) -36 b(w)434 b(long)g(it)g(tak)-36 b(es)434 b(to)f(get)h(the)f (certi\257cate.)2128 16589 y(W)-108 b(e)401 b(no)-36 b(w)400 b(create)h(a)g(graph)f Fs(G)g Ft(so)h(that)f(eac)-36 b(h)400 b(elemen)-36 b(t)400 b(in)h Fs(S)477 b Ft(is)401 b(a)g(v)-36 b(ertex)401 b(of)g Fs(G)p Ft(,)407 b(and)400 b(an)-36 b(y)401 b(t)-36 b(w)g(o)401 b(v)-36 b(ertices)800 18139 y(are)496 b(connected)e(if)i(and)f(only)h(if)g(an)-36 b(y)496 b(com)-36 b(bination)495 b(of)h(three)f(di\256eren)-36 b(t)494 b(n)-36 b(um)g(b)36 b(ers)494 b(from)i(the)f(t)-36 b(w)g(o)496 b(lists)800 19689 y(can)422 b(form)g(a)f(quasi-sp)36 b(ecial)423 b(\(sp)36 b(ecial\))422 b(Brinkh)-36 b(uis)421 b(3-triple.)574 b(F)-108 b(or)422 b(example,)i(if)f([1)p Fs(;)221 b Ft(2)p Fs(;)g Ft(3])424 b(and)d([1)p Fs(;)221 b Ft(2)p Fs(;)g Ft(4])425 b(are)800 21239 y(v)-36 b(ertices)411 b(of)h(the)e(graph,)415 b(they)c(can)f(b)36 b(e)411 b(connected)f(if)h (and)f(only)h(if)h([1)p Fs(;)221 b Ft(3)p Fs(;)g Ft(4])413 b(and)e([2)p Fs(;)221 b Ft(3)p Fs(;)g Ft(4])413 b(are)e(v)-36 b(ertices)411 b(of)800 22788 y(the)425 b(graph)h(to)36 b(o.)576 b(And)425 b(in)h(this)g(case,)i(the)d(four)h(v)-36 b(ertices)426 b(will)h(form)g(a)f(complete)g(graph.)575 b(No)-36 b(w)427 b(w)-36 b(e)426 b(ha)-36 b(v)g(e)800 24338 y(reduced)432 b(the)g(problem)g(in)-36 b(to)433 b(\257nding)e(the)h(largest)i(complete)f(subgraph)e(of)j(a)f(graph,)f (whic)-36 b(h)433 b(is)g(kno)-36 b(wn)800 25888 y(to)448 b(b)36 b(e)448 b(NP-complete,)k(in)c(p)36 b(olynomial)450 b(time.)623 b(Although)447 b(what)i(w)-36 b(e)448 b(did)g(do)36 b(es)448 b(not)g(imply)h(the)f(original)800 27438 y(problem)488 b(to)g(b)36 b(e)487 b(NP-complete,)502 b(it)488 b(do)36 b(es)488 b(shed)g(some)g(ligh)-36 b(t)488 b(on)g(ho)-36 b(w)488 b(to)g(solv)-36 b(e)489 b(the)f(problem:)686 b(w)-36 b(e)489 b(will)800 28987 y(use)433 b(the)g(bac)-36 b(ktrac)g(king)435 b(metho)36 b(d)433 b(to)g(\257nd)g(the)g(largest)h (Brinkh)-36 b(uis)433 b(triple.)2128 30537 y(W)-108 b(e)362 b(sa)-36 b(y)361 b(a)h(n)-36 b(um)g(b)36 b(er)360 b Fs(i)g Ft(is)i(compatible)f(with)h(a)f(list)h(of)g(n)-36 b(um)g(b)36 b(ers)359 b Fs(i)33789 30736 y Fq(1)34315 30537 y Fs(;)221 b(:)g(:)g(:)j(;)d(i)37672 30736 y Fr(n)38659 30537 y Ft(if)362 b(an)-36 b(y)362 b(three)e(w)-36 b(ords)361 b(c)-36 b(hosen)800 32087 y(from)521 b(the)e(corresp)36 b(onding)520 b(w)-36 b(ords)520 b Fs(w)19469 32286 y Fr(i)19845 32087 y Fs(;)221 b(w)21357 32286 y Fr(i)21677 32409 y Fl(1)22194 32087 y Fs(;)g(:)g(:)g(:)j(;)d(w)26037 32286 y Fr(i)26357 32397 y Fi(n)27499 32087 y Ft(can)521 b(form)f(a)h(quasi-sp)36 b(ecial)521 b(\(sp)36 b(ecial\))520 b(Brinkh)-36 b(uis)800 33637 y(3-triple.)2128 35186 y(Assuming)568 b(all)h(the)f(n)-36 b(um)g(b)36 b(ers)566 b(in)i(the)g(v)-36 b(ertices)568 b(are)g(ordered)g(increasingly)-108 b(,)602 b(w)-36 b(e)569 b(try)f(to)g(construct)800 36736 y(the)553 b(largest)h(quasi-sp)36 b(ecial)555 b(\(sp)36 b(ecial\))554 b(Brinkh)-36 b(uis)553 b(triples)h(recursiv)-36 b(ely:)819 b(W)-108 b(e)554 b(start)f(with)h(the)f(pair)g(of)800 38286 y(n)-36 b(um)g(b)36 b(ers,)473 b Fs(a)7131 38485 y Fq(1)8123 38286 y Ft(and)466 b Fs(a)11368 38485 y Fq(2)11894 38286 y Ft(,)474 b(who)467 b(has)f(the)g(largest)h(set)f(of)h (compatible)g(n)-36 b(um)g(b)36 b(ers)465 b(of)i(all)g(pairs)g(of)g(n) -36 b(um)g(b)36 b(ers)800 39836 y(in)384 b Fo(f)p Ft(1)p Fs(;)221 b(:)g(:)g(:)j(;)d(m)p Fo(g)p Ft(.)563 b(After)384 b(w)-36 b(e)384 b(ha)-36 b(v)g(e)384 b(a)h(list)f Fs(a)21224 40035 y Fq(1)21750 39836 y Fs(;)221 b(:)g(:)g(:)j(;)d(a)25346 40035 y Fr(n)p Fm(\241)p Fq(1)27559 39836 y Ft(suc)-36 b(h)383 b(that)g(ev)-36 b(ery)385 b(three)f(n)-36 b(um)g(b)36 b(ers)382 b(in)i(the)g(list)g(can)800 41385 y(form)454 b(a)f(quasi-sp)36 b(ecial)455 b(\(sp)36 b(ecial\))454 b(Brinkh)-36 b(uis)453 b(3-triple,)458 b(w)-36 b(e)454 b(try)f(to)g(\257nd)f Fs(a)37753 41584 y Fr(n)38833 41385 y Ft(as)i(the)e(n)-36 b(um)g(b)36 b(er)452 b(suc)-36 b(h)453 b(that)800 42935 y Fs(a)1483 43134 y Fr(n)2553 42935 y Ft(is)445 b(compatible)f(with)h Fs(a)14187 43134 y Fq(1)14712 42935 y Fs(;)221 b(:)g(:)g(:)j(;)d(a)18308 43134 y Fr(n)p Fm(\241)p Fq(1)20137 42935 y Ft(,)447 b(and)d Fs(a)24168 43134 y Fq(1)24694 42935 y Fs(;)221 b(:)g(:)g(:)i(;)e(a)28289 43134 y Fr(n)29360 42935 y Ft(has)444 b(the)g(largest)h(p)36 b(ossible)445 b(set)f(of)h (compatible)800 44485 y(n)-36 b(um)g(b)36 b(ers.)886 b(If)537 b(there)f(is)h(a)g(tie,)563 b(w)-36 b(e)536 b(c)-36 b(ho)36 b(ose)537 b(the)f(smallest)i(p)36 b(ossible)537 b(n)-36 b(um)g(b)36 b(er.)885 b(Once)536 b(w)-36 b(e)537 b(cannot)g(add)800 46035 y(another)357 b(n)-36 b(um)g(b)36 b(er)357 b(to)g(the)h(curren)-36 b(t)356 b(list)i(of)h Fs(a)22457 46234 y Fq(1)22982 46035 y Fs(;)221 b(:)g(:)g(:)j(;)d(a) 26578 46234 y Fr(n)27205 46035 y Ft(,)373 b(w)-36 b(e)358 b(ha)-36 b(v)g(e)358 b(found)f(a)h(\\lo)36 b(cally)361 b(optimal")d(Brinkh)-36 b(uis)800 47584 y Fs(n)p Ft(-triple.)874 b(W)-108 b(e)533 b(then)e(bac)-36 b(ktrac)g(k)533 b(to)g Fs(a)20076 47783 y Fr(n)p Fm(\241)p Fq(1)22436 47584 y Ft(and)f(searc)-36 b(h)532 b(for)h(the)f(next)g(b)36 b(est)532 b(c)-36 b(hoice)533 b(of)g Fs(a)45674 47783 y Fr(n)46300 47584 y Ft(.)874 b(When)532 b(all)800 49134 y(suc)-36 b(h)457 b(c)-36 b(hoices)458 b(are)h(analyzed,)465 b(w)-36 b(e)458 b(bac)-36 b(ktrac)g(k)459 b(to)f Fs(a)26315 49333 y Fr(n)p Fm(\241)p Fq(2)28143 49134 y Ft(.)652 b(W)-108 b(e)457 b(rep)36 b(eat)458 b(the)g(pro)36 b(cess)458 b(un)-36 b(til)457 b(w)-36 b(e)458 b(bac)-36 b(ktrac)g(k)800 50684 y(to)488 b Fs(a)3127 50883 y Fq(1)4141 50684 y Ft(and)g Fs(a)7408 50883 y Fq(2)7933 50684 y Ft(,)502 b(when)488 b(w)-36 b(e)488 b(try)h(the)e(pair)h(of)h(n)-36 b(um)g(b)36 b(ers)487 b(who)h(has)g(the)g(next)g(largest)h(set)f(of)h (compatible)800 52234 y(n)-36 b(um)g(b)36 b(ers.)550 b(W)-108 b(e)352 b(will)h(con)-36 b(tin)g(ue)351 b(un)-36 b(til)352 b(all)h(the)e(p)36 b(ossibilities)353 b(are)g(considered.)550 b(Of)352 b(course,)369 b(w)-36 b(e)352 b(can)g(alw)-36 b(a)g(ys)800 53783 y(break)370 b(out)g(of)g(the)g(searc)-36 b(h)369 b(if)i(the)e(size)i(of)f(the)g(list)g(of)g(n)-36 b(um)g(b)36 b(ers)369 b(found)g(plus)h(the)f(n)-36 b(um)g(b)36 b(er)368 b(of)j(compatible)800 55333 y(n)-36 b(um)g(b)36 b(ers)432 b(a)-36 b(v)-72 b(ailable)435 b(is)f(less)g(than)f(the)g(b)36 b(est)433 b(kno)-36 b(wn)434 b(size)g(of)g(the)f(triples)h(at)g(the)f (time.)2128 56883 y(The)481 b(complexit)-36 b(y)482 b(of)g(searc)-36 b(hing)481 b(the)f(largest)h(complete)g(subgraph)f(of)i Fs(n)f Ft(v)-36 b(ertices)481 b(is)g(equiv)-72 b(alen)-36 b(t)482 b(to)800 58433 y(searc)-36 b(hing)432 b(the)g(largest)h(indep) 36 b(enden)-36 b(t)430 b(set)i(of)h(v)-36 b(ertices)432 b(of)h(the)f(complemen)-36 b(t)432 b(of)h(the)e(graph,)i(whose)f Fj(av-)800 59982 y(er)-66 b(age)486 b Ft(rate)h(of)g(gro)-36 b(wth)487 b(is)g(sub)36 b(exp)g(onen)-36 b(tial,)501 b(i.e.,)g Fs(O)36 b Ft(\()p Fs(n)28504 59500 y Fq(log)172 b Fr(n)30503 59982 y Ft(\).)738 b(Ho)-36 b(w)g(ev)g(er,)501 b(the)486 b(exact)i(amoun)-36 b(t)486 b(of)i(lab)36 b(or)800 61532 y(required)372 b(for)g(a)g(sp)36 b(eci\257c)372 b(kind)g(of)g(graphs)g(can)g(b)36 b(e)371 b(v)-36 b(ery)373 b(exp)36 b(onen)-36 b(tial.)558 b(Theoretically)-108 b(,)386 b(w)-36 b(e)372 b(can)g(tak)-36 b(e)373 b(ad-)800 63082 y(v)-72 b(an)-36 b(tage)332 b(of)h(the)e(sp)36 b(ecial)333 b(structure)e(of)h(the)g(graphs)f(to)h(increased)g(the)f(p) 36 b(erformance:)528 b(if)333 b(v)-36 b(ertices)332 b([1)p Fs(;)221 b Ft(2)p Fs(;)g Ft(3])800 64632 y(and)368 b([4)p Fs(;)221 b Ft(5)p Fs(;)g Ft(6])372 b(are)d(connected,)381 b(there)368 b(is)i(automatically)g(a)f(complete)g(subgraph)f(of)h(20)h (v)-36 b(ertices,)382 b(namely)800 66181 y(an)-36 b(y)529 b(com)-36 b(binations)529 b(of)g(three)f(n)-36 b(um)g(b)36 b(ers)527 b(from)j(1)f(to)g(6.)864 b(But)528 b(suc)-36 b(h)528 b(an)g(approac)-36 b(h)529 b(will)h(use)e(recursiv)-36 b(e)800 67731 y(programming,)426 b(whic)-36 b(h)424 b(w)-36 b(ould)424 b(ha)-36 b(v)g(e)424 b(required)f(exp)36 b(onen)-36 b(tial)425 b(space)f(and)f(th)-36 b(us)423 b(is)h(impractical.)576 b(Unless)800 69281 y(w)-36 b(e)469 b(can)g(\257nd)f(other)h(metho)36 b(ds)468 b(to)h(\257nd)f(the)g(lo)-36 b(w)g(er)470 b(b)36 b(ound,)477 b(using)469 b(Brinkh)-36 b(uis)468 b(triples)h(cannot)g (pro)-36 b(vide)p Black Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black 800 -3114 a Fn(8)p Black 800 -458 a Ft(m)-36 b(ust)504 b(b)36 b(etter)503 b(results,)523 b(ev)-36 b(en)504 b(with)h(more)f(p)36 b(o)-36 b(w)g(erful)505 b(\(m)-36 b(ulti-pro)36 b(cessor\))504 b(computers.)790 b(Unfortunately)-108 b(,)800 1092 y(this)433 b(is)h(the)f(b)36 b(est)433 b(metho)36 b(d)433 b(kno)-36 b(wn)434 b(y)-36 b(et,)434 b(if)h(not)e(the)g(only)h(one.)2128 2642 y(The)693 b(Maple)g(pac)-36 b(k)-72 b(age)693 b(and)f(the)g (results)h(on)f(optimal)h(Brinkh)-36 b(uis)693 b(triples)f(are)h(all)h (a)-36 b(v)-72 b(ailable)694 b(at)p 0 1 0 0 TeXcolorcmyk 800 4192 a Fh(http://www.math.temple.edu/)p Fo(\273)p Fh(xysun/ternarysf/ternary)p 36115 4192 411 45 v 470 w(square)p 40689 4192 V 489 w(free.htm)p [[79 679 491 691] [1 1 1 [3 3]] [0 0 1]] (http://www.math.temple.edu/~xysun/ternarysf/ternary_square_free.htm) pdfm Black Ft(.)19675 6826 y(4.)651 b Fp(A)-39 b(ckno)-30 b(wledgement)2128 9151 y Ft(Man)-36 b(y)384 b(thanks)f(to)g(Doron)h (Zeilb)36 b(erger)384 b(for)f(his)h(encouragemen)-36 b(ts,)393 b(to)383 b(Uw)-36 b(e)384 b(Grimm)e(for)i(p)36 b(oin)-36 b(ting)383 b(out)800 10700 y(an)361 b(error)f(in)h(the)f (\257rst)g(attempt,)375 b(and)361 b(to)f(Li)h(Zhang)g(for)g(his)g (useful)f(discussions)h(and)f(commen)-36 b(ts)361 b(during)800 12250 y(the)377 b(dev)-36 b(elopmen)g(t)377 b(of)h(the)f(programs.)560 b(Also)379 b(thanks)e(to)h(the)f(referees)g(who)h(pro)-36 b(vided)377 b(suggestions)i(that)800 13800 y(made)433 b(this)h(pap)36 b(er)433 b(more)h(informativ)-36 b(e)434 b(and)f(readable.)22927 16434 y Fp(References)p Black 800 18538 a Fg(1.)p Black 554 w(M.)486 b(Baak)-31 b(e,)517 b(V.)486 b(Elaser)g(and)g(U.)g(Grimm,)516 b(The)485 b(en)-31 b(trop)g(y)487 b(of)f(square-free)f(w)-31 b(ords,)516 b Ff(Math.)502 b(Comput.)i(Mo)-57 b(del)57 b(ling)583 b Fe(26)2214 19866 y Fg(\(1997\),)373 b(13{26.)p Black 800 21194 a(2.)p Black 554 w(F.-J.)333 b(Branden)-31 b(burg,)341 b(Uniformly)334 b(gro)-31 b(wing)335 b Fd(k)21717 20793 y Fc(th)22957 21194 y Fg(p)31 b(o)-31 b(w)g(er-free)333 b(homomorphisms,)343 b Ff(The)-57 b(or)g(et.)363 b(Comput.)f(Sci.)334 b Fe(23)g Fg(\(1983\),)2214 22523 y(69{82.)p Black 800 23851 a(3.)p Black 554 w(J.)370 b(Brinkh)-31 b(uis,)370 b(Nonrep)31 b(etitiv)-31 b(e)371 b(sequences)e(on)g(three)g(sym)-31 b(b)31 b(ols,)371 b Ff(Quart.)395 b(J.)i(Math.)e(Oxfor)-57 b(d)483 b Fe(34)370 b Fg(\(1983\),)i(145{149.)p Black 800 25179 a(4.)p Black 554 w(M.)331 b(Cro)31 b(c)-31 b(hemore,)340 b(Sharp)331 b(c)-31 b(haracterizations)333 b(of)e(squarefree)g(morphisms,)339 b Ff(The)-57 b(or)g(et.)362 b(Comput.)f(Sci.)332 b Fe(18)f Fg(\(1982\),)342 b(221{)2214 26508 y(226.)p Black 800 27836 a(5.)p Black 554 w(S.)384 b(B.)g(Ekhad)g(and)f(D.)h(Zeilb)31 b(erger,)388 b(There)383 b(are)g(more)g(than)h(2)28741 27434 y Fc(n=)p Fb(17)31064 27836 y Fd(n)p Fg(-letter)g(ternary)f(square-free)g(w)-31 b(ords,)388 b Ff(J.)409 b(Inte)-57 b(ger)2214 29165 y(Se)g(q.)371 b Fe(1)f Fg(\(1998\),)i(Article)e(98.1.9.)p Black 800 30493 a(6.)p Black 554 w(S.)247 b(Finc)-31 b(h,)271 b(P)-31 b(attern-free)248 b(w)-31 b(ord)246 b(constan)-31 b(ts,)p 0 1 0 0 TeXcolorcmyk 273 w Fa (http://pauillac.inria.fr/algo/bsolve/constant/words/words.html)p [[256 443 580 455] [1 1 1 [3 3]] [0 0 1]] (http://pauillac.inria.fr/algo/bsolve/constant/words/words.html) pdfm Black Black 800 31821 a Fg(7.)p Black 554 w(John)389 b(No)31 b(onan)390 b(and)f(Doron)g(Zeilb)31 b(erger,)395 b(The)389 b(Goulden-Jac)-31 b(kson)390 b(cluster)e(metho)31 b(d:)533 b(extensions,)395 b(applications)d(and)2214 33150 y(implemen)-31 b(tations,)374 b Ff(J.)397 b(Di\256er.)f (Equations)g(Appl.)369 b Fe(5)h Fg(\(1999\),)i(355{377.)p Black 800 34478 a(8.)p Black 554 w(Uw)-31 b(e)483 b(Grimm,)512 b(Impro)-31 b(v)g(ed)483 b(b)31 b(ounds)482 b(on)g(the)h(n)-31 b(um)g(b)31 b(er)482 b(of)h(ternary)f(square-free)g(w)-31 b(ords,)511 b Ff(J.)501 b(Inte)-57 b(ger)500 b(Se)-57 b(q.)484 b Fe(4)f Fg(\(2001\),)2214 35806 y(Article)371 b(01.2.7.)p Black 800 37135 a(9.)p Black 554 w(Mic)-31 b(hel)370 b(Lecon)-31 b(te,)371 b(A)e(c)-31 b(haracterization)372 b(of)e(p)31 b(o)-31 b(w)g(er-free)369 b(morphisms,)i Ff(The)-57 b(or)g(et.)396 b(Comput.)h(Sci.)370 b Fe(38)g Fg(\(1985\),)i(117{122.)p Black 800 38463 a(10.)p Black 555 w(M.)d(Lothaire,)i Ff(Combinatorics)396 b(on)h(Wor)-57 b(ds)p Fg(,)368 b(Addison-W)-92 b(esley)g(,)370 b(1983.)p Black 800 39791 a(11.)p Black 555 w(W)-92 b(olfram)370 b(Researc)-31 b(h,)369 b(Squarefree)g(w)-31 b(ord,)p 0 1 0 0 TeXcolorcmyk 371 w Fa (http://mathworld.wolfram.com/SquarefreeWord.html)p [[259 359 510 371] [1 1 1 [3 3]] [0 0 1]] (http://mathworld.wolfram.com/SquarefreeWord.html) pdfm Black 800 41399 52000 45 v 800 43406 a Ft(2000)435 b Fj(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Ft(:)577 b(Primary)434 b(05A20;)h(Secondary)e(68R15.)800 44956 y Fj(Keywor)-66 b(ds:)597 b(squar)-66 b(e-fr)g(e)g(e,)463 b(ternary,)h(wor)-66 b(d,)464 b(Brinkhuis)h(triple)p 800 46343 V 800 48424 a Ft(\(Concerned)433 b(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A006156)p 16090 48637 4878 54 v [[217 281 261 293] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A006156) pdfm Black 2 w(.\))p 800 49886 52000 45 v 800 52693 a(Receiv)-36 b(ed)428 b(No)-36 b(v)g(em)g(b)36 b(er)427 b(21,)i(2002;)h(revised)e(v) -36 b(ersion)427 b(receiv)-36 b(ed)427 b(August)f(1,)j(2003;)i (Published)426 b(in)h Fj(Journal)800 54243 y(of)465 b(Inte)-66 b(ger)462 b(Se)-66 b(quenc)g(es)p Ft(,)432 b(August)h(18,)i(2003.)p 800 55630 V 800 57637 a(Return)e(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 198 338 210] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black Black eop %%Trailer end end