The Traveling Salesman Problem and harmonic analysis

Publicacions Ma emá iques, Vol 35 (1991, 259-267 . THE TRAVELING SALESMAN PROBLEM AND HARMONIC ANALYSIS PETER W . JONES In his pape we p opose o discuss some ela ionships be ween he classical T a eling Salesman P oblem (TSP), Li lewood-Paley heo y, and ha monic measu e . This ci cle o ideas is also closely ela ed o he heo y o Cauchy in eg als on Lipschi z g aphs, and his aspec is discussed mo e ully in he pape o Da id and Semmes [2] in hese p ioceedings . The main di e ences be ween he subjec s o [2] and his pape a e ha he esul s he e a e alid o one dimensional se s, whe eas [2] ea s d dimensional se s . The se s conside ed in [2] a e equi ed o sa is y he na u al hickness condi ion o Da id- ype, while he se s conside ed he e ha e no such es ic ion . The eason Da id and Semmes ha e such a es ic ion is hei in e es in boundedness o singula in eg als . While we a e also in e es ed in his p oblem and he ela ed p oblem o analy ic capaci y, singula in eg als do no play qui e as s ong a óle in he opics discussed he e . Le us begin by ecalling he classical TSP . Le K = {x 1 ,.. . , x } be a ini e collec ion o poin s in R 2 . Find ]Ph, he sho es Hamil onian cycle passing h ough K, and le l(Ph) deno e i s a cleng h . This is a "ha d" p oblem, and i seems unlikely ha we will e e see a as algo i hm o sol ing i . On he o he hand, conside he p oblem o inding he sho es connec ed se F o which con ains K . Then as algo i hms exis o compu ing F o , and since i is easily shown ha l(Ph) < 2l(Po), he ha monic analys who does no conside cons an s o be impo an migh conside he ini e TSP o be sol ed . (See [7] o mo e in o ma ion on he classical TSP .) In wha e e o m i is posed, he classical TSP may seem unna u al o ha - monic analys s because o he es ic ion ha K is ini e . We conside ins ead gene al se s K and pose he ollowing ques ion : can we ind, up o a cons an mul iple, he leng h o he sho es cu e which passes h ough K? Recall ha a cu e P is called ec i iable i P = F([0, A]) o some A <-óo whe e F is Lip- schi z, ¡F(x) - F(y)j < Ix - y¡ . I is no oo ha d o see ha P is a ec i iable cu e i and only i P is connec ed and he one dimensional Hausdo measu e o P is ini e, l(P) < oo . A es a emen o ou p oblem is hus he ollowing : cha ac e ize subse s o ec i iable cu es . I is pe haps su p ising ha his p ob- lem has a a he simple answe in e ms o a geome ic Li úewood-Paley ype 26 0  P .W . JONES heo y . Such an app oach was i s p esen ed o he special case o Lipschi z cu es in he P oceedings o he p e ious El Esco ial mee ing [5] . The poin o ha a gumen was o gi e ano he p oo o boundedness o Cauchy in eg als by examining geome ic squa e unc ions . I K CL whe e L is a line, ou p oblem is easily sol ed . We he e o e should a emp o see how much K de ia es om lines a all poin s o K and a all scales . We de ine o a dyadic squa e Q he quan i y ,3K(Q) = in  sup  l(Q) -1 dis an e (z, L), -cKn3Q whe e l(Q) = 2 - n is he sideleng h o Q and whe e 3Q is he squa e wi h same cen e as Q and l(3Q) = 3l(Q) ( he in imum is aken o e all lines L .) Then i u ns ou ha K C I', I' a ec i iable cu e i and only i K is bounded and 02(x) --- 1 : p 2 (Q)l(Q) < 0(), Q whe e he sum is aken o e all dyadic Q . We ema k ha p2(K) is easily seen o be equi alen o pK(z, ) -2 dx dy d >0 IR2 whe e IC(z, ) is de ined using he disk {cp : ico - z1 < } ins ead o a squa e Q . The eason o choosing ou de ini ion is pu ely psychological ; i is help ul when coun ing Whi ney squa es . Le P 0 deno e he sho es cu e con aining K . Theo em 1 . [6] The e is a uni e sal cons an C 0 such ha o all K, C~ 1 < diame e (K) -h P 2 (K) < C . l(I70)  0 I ha e been in o med by S .Y . Chang and J . Ga ne ha hei s uden K . Okikiolu has ex ended Theo em 1 o be alid in Rn, n >_ 3 . This in ol es inding a di e en p oo o he second inequali y o a bi a y cu es 0 . The i s implica ion o Theo em 1 is ob ained by gi ing a di ec cons uc ion o a cu e I' such ha l(I') <_ Co(diam (K) -F- p2 (K» . Wi hou being oo speci ic, ou me hod is closely ela ed o he ollowing algo i hm . Suppose K is closed, and suppose cu es I' 1 , I' 2 , . . . , n ha e been cons uc ed, such ha k consis s o k line segmen s I~ wi h endpoin s on K . Le xn+1 E K ha e maximal dis an e o he collec ion o all endpoin s o he in e als I j n . Now eplace in he mos e iicien manne one o he in e als I j nby wo in e als so as o ob ain a new cu e n+1 which also con ains xn+l . As an easy example suppose K consis s o h ee poin s, K = {0,1,1 2 + ib} whe e 0 < 6 « 1 . Then clea ly THE TRAVELING SALESMAN PROBLEM  26 1 Fo = [0,1/2 + i5] U [1/2 + i5, l] . Take 1 = [0,1] so ha 1(1 7 1 ) = diame e K . Then he algo i hm gi es 1 7 2 as ou desi ed o . Also no ice ha 1( 2) = 1 (P1) + (1( 2 ) - 1( 1)) = diame e (K) + (  1 _ +45 2 - 1) - diame e (K) +62 diame e (h) + 02 ([0, 1]2)1([0, 1]2) . Fo mo e gene al K, a a ian o his algo i hm wo ks (essen ially) because o he cons uc ed cu es P ., l(I'n+1) -1 ( n) <C 2 (Q~)l(Q  ), and each Q~ is coun ed only a ini e numbe o imes . Thus se ing I 7 = lim I 7 n (assuming ha makes sense), l(P) _< 1(1 7 1 ) + En° 1(1(F~+1) - 1(I'~)) < diame e (K) + C j :Q 9K(Q)1(Q) . This is in any case he idea we use . The p oo o he second inequali y in Theo em 1 uses a di e en idea . One i s no ices ha he esul ollows om a ca e ul applica ion o he Py hago ean heo em i K is he bounda y o a Lipschi z domain . One hen uses he ollowing esul . Theo em 2 . Suppose 9 is a simply connec ed domain . Then SZ =  U Ii  n 52 (i ) whe e {Qj} is a disjoin collec ion o C o Lipschi z domains wiih he p ope y ha each Qi C 52 and each z E 9 i,s in no mo e han Co o he se s Sli . Fu he mo e, Y~ 1(aQ i ) < Co1(as2) . .i See [4] whe e his is ex ended o minimal 2 su aces . One now comple es he p oo o Theo em 1 by using Theo em 2 and he ac ha he esul is ue o Lipschi z cu es . To be a li le mo e p ecise, ake a cu e I' and enla ge i by Theo em 2 o a cu e I", 1( ') <C o l(1 7 ), such ha C P' = UQi is a union o Lipschi z domains plus a disk a oo . I Pj(Q) is he "/l" compu ed o aQ i and Q, E02 (Q)1(Q) < Cl(^) . Q When one compu es ,l's o P', he cu es a9 i essen ially ac independen ly so ha (mo ally) (Q) l C pj(Q) . i 26 2 P .W . JONES Some mino adjus men s a e o cou se needed o make his idea wo k . In any case, one ends up wi h he es ima e l2(F) --_ ~ 22(Q)1(Q) :~ C  ~~ (Q)l(Q) Q  9Q < c2 1 : 1(aq ; ) We men ion an amusing co olla y I FC R2 is connec ed, he e is a and such ha any poin s x, y E F' 1(?') < 3Ix - y¡ . < 2C21(F1) < 2C31(F) . o Theo em 2 : connec ed se F' such ha 1(11 1 ) < Col(F) can be connec ed by an a c -y C F' wi h We o e a ewa d o $100 o anyone who p o ides a p oo o his esul which does no use L 2 es ima es . (Admi edly, his is no p ecisely de ined .) In [1] Ch is ophe Bishop and his au ho use Theo em 1 o deduce some new esul s on ha monic measu e . The main esul p o ed he e is he ollowing . Theo em 3 . Suppose SZ is simply connec ed and z o E 9 sa is ies dis an e (z o , 02) = 1 . Then i F is any ec i iable cu e, and E C 11(1 052, 3 Theo em 4 . Fo a cu e F, i and only i w xo (E) < 6(1(E), 1(09» . He e w zo deno es ha monic measu e o SZ measu ed a z o , and o 1(052) < A, 6( , 1(09» < b( , A) ó 0 . The p o o ypical such esul is he classical o m o he F .M . Riesz heo em due o Lau en ie : when 11 = OS2 and E C I', w zo (E) <_  Cplog(1(I7)) 1 log(1(E))1 + 1 Theo em 3 had been conjec u ed by Oksendal, who p o ed i in he case whe e 1(E) = 0 and' F = R . La e esul s o special cu es F a e due o Kau man, and Wu . See [1] o a mo e comple e his o y . A a he easy co olla y o Theo em is sup l«ñ -1 (11 n SZ)) < o0 n ,D sup -11 ({( E F : Iz - (1 < }) < co . z, THE TRAVELING SALESMAN PROBLEM  263 He e he i s sup emum is aken o e all simply connec ed 52 and all Riemann mappings (P om he uni disk o 52 . The cu es sa is ying he second inequal- i y o he heo em a e hose sa is ying he Guy Da id (o "Ahl o s-Da id") condi ion ; hey we e shown by Da id o be exac ly he cu es o which he Cauchy in eg al is L2 bounded . The i s conclusion o Theo em 4 was i s p o en by Hayman andWu, and a li le la e by Ga ne , Geh ing, and Jones, when one has IP = R . This was ex ended o cho d a e cu es I' by Fe nández and Hamil on . Again, see [1] o a mo e de ailed his o y . The p oo o Theo em 3 is a he long and complica ed, bu he main idea can be a he easily explained . Le 52, I' be ixed and suppose E C I' n 09 sa is ies w, (E) > so . Le P : D -+ C E be he uni e sal co e ing map (we may assume E is closed), and le ~¿(0) = z o . Se ing D = <P - 1 (Q) (le 0 E D o make his well de ined), we see by he maximum p inciple ha 1(aD n T) > 27 eo . A heo em due o Pomme enke [8] allows one o conclude ha whe e 1 is he no mal undamen al domain associa ed o 4> and C E . Since T has bounda y consis ing o a subse o T plus some ci cula a es o hogonal o T, 1(aT) < 7 2 , and he ha monic measu e in T (measu ed a he o igin) o T n 01 is g ea e han el = el (so) . We may hus assume ha Then i u ns ou ha 1(áT n T) > 27 eo, I i we e he case ha l(á(4>(T») < oo, one could simply in oke he F .M . Riesz-Lau en ie heo em o ob ain Theo em 3 . This u ns ou o be alse, bu a closely ela ed esul is ue . Le D be a Lipschi z domain, D C 1 and o e e y z E D, w z ,D(T n 8D) > e2 . 1(,9(,¿(D») :5 C(E2), and his es ablishes Theo em 3 . The di icul pa o he a gumen is o p o e he las inequali y . To his end se V(z) = ew(z) and de ine d(z) = dis ance (z, aT) . Then he now well known LZ heo y applied o (j>') 1 / 2 ells us 1(á5(D)) - ¡V(0)¡ + JID I ~I (x)IIWI(z)I2d(z) dx dy . Applying he L2 inequali y once mo e yields 1(5(D» , ., IV(0)I + IV'(0)I -F A I,¿,(z)IIw"(z) + 1(WI(z))2I2d(z)3 dx dy . 26 4  P .W . JONES The i s wo e ms a e " i ial", and we a e le wi h he ask o bounding he las in eg al . Fo easons o be explained we now change he plus sign in he in eg al o a minus sign, and calling he in eg al I, we ob ain I -i(z)II_  W"(z) - 1 ( , P'(z» Z j'd(z) s dx dy D +"O he e m" . I u ns ou ha he wo e ms abo e look qui e di e en and equi e di e en a gumen s . We will no explain how o bound he "O he Te m", and will concen a e on he i s . A su p ising ac is ha al hough he mapping W"(z) + 1/2(,p'(z))2 ---, W"(z) _ 112(W' (Z»2 is se iously nonlinea , he e is none he less an L 2 heo y (a leas o "nea ly" uni alen 1P) o he mapping (,p'(z»1 /2(~O"(z) + 112(W' (Z»2) _ (D'(z»1/2(,"(z) _ 1/2(~p'(z»2) . Why ha e we changed he plus sign o a minus? The answe is ha (P" - 1/2(W1)2 = ( V ) 1 _ 2 ( y, ) 2 = S4) is he Schwa zian o ¿, and So¿ is ela ed o geome y! In pa icula S , ¿ - 0 when %P is a Mdbius ans o ma ion . Now ou <P is associa ed o E, a subse o a ec i iable cu e, and by Theo em 1, E looks " la mos o he ime" . In pa icula , i z E D, he condi ion w(4>(z), E, 52) > e implies ha he e mus be a a he la ge amoun o E (in some dense) a 4>(z), on scale dis an e (4)(z), E) - ¡V (z) id(z) . (This ela ion "-" is jus he Koebe 1/4 heo em plus ou choice o he de i- ni ion o D) . Now since E is "mos ly ia " and "dense nea (P(z)" we mo ally ha e ha E . : s aigh line nea -P(z) . This would o e S-P(z) Pd 0 because 11 would be nea ly a Mdbius ans o ma ion nea z . We now a emp o quan i y he aboye in ui ion . Le R C T be a squa e in he Whi ney decomposi ion o T, and assume ha R n D :~ 0 . Then 4)(R) has diame e - ¡V(z)Id(z) - dis an e (4>(R), E) . Le Q be a dyadic squa e, <P(R) l Q :~ 0, l(Q) - A diame e (4>(R)) whe e A is a la ge ixed cons an . Then while we canno expec S4> - 0 on R, i u ns ou ha "Highe O de Te m" on all o R . Igno ing he "Highe O de Te m" we see ha essen ially and summing o e all R we ind ha " o i s o de ", he Lipschi z cons an o OL . THE TRAVELING SALESMAN PROBLEM  26 5 I S 4 >(z)I d(z)2 < COOE(Q) I R Iq>'(z)IISp(z)12d(z)3 dx dy < C00 2 (Q)l(Q) JID ¡V(z) IIS , ¿ 1 2 d(z) 3 dx d y <C a E p 2 (Q)l(Q) Q < C l(I') . While ou easoning was a bi imp ecase, he las inequali y is ac ually ue . As we ema ked ea lie , i is un o una e ha a his poin in ime we know o no elemen a y a gumen s o p o e Theo em 3 . We now a emp o explain ou mys e ious ema k ha he so-called "O he Te m" can be igno ed in he p oo o Theo em 3 . Le L be a Lipschi z domain and again se d(z) = dis ance (z, aL) . The ollowing, as ye unpublished esul o Bishop and he au ho was p o en only in 1990 . Theo em 5 . Suppose d> is uni alen on L and JIL IV(z)IISP(z)I2d(z)3 dx dy - B< oo, Then V E Hi12-E(L) wi h no m depending only on V (cen e o L), B, e, and No ice ha he space H'Is-E i s sha p : conside a MSbius ans o ma ion . The assump ion ha ~¿ is uni alen can be elaxed o he condi ion ha co is a Bloch unc ion, bu his is no undamen ally di e en . To p o e Theo em 3, we use he ac , as ou lined abo e, ha he in eg al in Theo em 5 is bounded . Thenwe simply apply Jensen's inequali y . An un o una e ac o ou p esen p oo o Theo em 5 is ha i is e y simila o ou p e ious p oo ha he so-called "O he Te m" is bounded . (We do, howe e , a oid a a he delica e geome ic a gumen which was used o "O he Te m" .) Finally, we wish o close wi h some c yp ic commen s . In [5], he bound- edness o he Cauchy in eg al was ( e) s udied by essen ially showing ha he 26 6  P .W . JONES Cauchy in eg al ope a o on a Lipschi z cu e could be w i en as a sum o a "diagonal" ope a o ( he Hilbe ans o m) and an "o diagonal" ope a o (a pa ap oduc ) . While his philosophy was by no means new, he no el y was ha he pa ap oduc co esponded o he numbe p2( F) in a e y well de ined manne . In a e y eal sense, Theo em 1 p o ides a way o associa e a pa ap oduc o any plana se . This imp ecise s a emen has been ex ensi ely de eloped by Da id and Semmes [3] . The s udy o q2 (K) and he Schwa zian, S-P, o a uni e sal co e ing map a e " he same" ia ' Theo em 2 and he p oo o Theo em 3 . Fu he mo e, he Schwa zian co esponds o a ce ain non~ linea pa ap oduc ia Theo em 5 . All objec s men ioned he e a e nonlinea Li lewood-Paley exp essions . The mi acle is ha , as i s shown o Cauchy in eg als, he nonlinea i y does no des oy he L 2 heo y . One can loosely explain his by saying ha he nonlinea e ec s a e con olled by L 2 bounds on geome y . We a e le wi h he ollowing diag am : 2 . 3 . 4 . 5 . 6 . l 2 (K) K The Cauchy in eg al Pa ap oduc  S<~ Re e ences C .J . BISHOP AND P.W . JONES, Ha monic measu e and a cleng h, Annals o Ma h . ( o appea ) (1990) . G . DAVID AND S . SEMMES, A icle in hese p oceedings . G . DAVID AND S . SEMMES, Au dela les g aphes Lipschi ziennes, p ep in . J .B . GARNETT, P.W . JONES AND D .E . MARSI1ALL, A Lipschi z decom- posi ion o minimal su aces, p ep in . P.W . JONES, "Squa e unc ions, Cauchy in eg als, analy ic capaci y, ajad ha monic measu e," Sp inge Lec u e No es in Ma h . 1384, 1989, pp . 24-68 . P.W . JONES, Rec i iable se s and he a elling salesman p oblem, In en- iones Ma h . (1990) . THE TRAVELING SALESMAN PROBLEM  267 7 .  E .L . LAWLER ET . AL ., "The a eling salesman p oblem," Wiley-In e s- cience, 1985 . 8 .  CH . POMMERENKE, On he G een's unc ion o Tuchsian g oups, Ann . Acad . Sci . Tenn . 2(1976), 409-427 . Ma hema ics Depa men Yale Uni e si y New lla en CT 06520 U .S .A .