Rigid Circle and Sphere Packings. Part II: Infinite Packings with Finite Motion

Rube Cunne//p Depa men o Ma hema ics Co nell Uni e si y I haca, N Y 14853 Pa ially suppo ed by N.S.F. g an , numbe MCS- 790251, as well as he I.H.E.S., Bu es-su -Y e e, F ance. Suppo was also gi en by he Uni e si y o Dijon, Sa oie Uni e si y in F ance, and he Max- Planck-Ins i u e u Ma hema ik a Bonn, Wes Ge many. Sub en ionnb, en pa ie, pa le N.S.F. (nume o de sub en ion MCS-790251), ainsi que pa I'I.H.E.S. a Bu es-su -Y e e, F ance. L'uni e si k de Dijon e I'uni e si b Sa oie en F ance, ie Max-Planck- Ins i u e u Ma hema ik a Bonn, en Allemagne de I'Oues , on aussi appo e leu appui. F ench ansla ion: T aduc ion angaise : Jean-Luc Raymond RIGID CIRCLE AND SPHERE PA CKINGS PART 11 : INFINITE PACKINGS WITH FINITE MOTION ABSTRACT A packing Po ci cles in he plane is called n-s able, o n = 1,2,. . . i e e y se o n ci cles is held ixed by he es . P is called ini ely s able i i is n-s able o e e y n = 1, 2,. . . Fo each o he 31 ami- lies o egula connec ed ci cle packings in he plane we classi y which a e ini ely s able and which a e no . Fo 3 o he cases when he amilies o packings a e no ini ely s able, i u ns ou ha he smalles n o which hey a e no n-s able ge s a bi a ily la ge, depending on a pa ame e o he amily. I INTRDDUCTION Suppose we ha e a packing o ci cles in he plane. How should we de ine wha i means o he packing o be s able? How do we calcula e when his happens? One eason o such ques ions is he main esul o pa I [4]. Roughly, i says ha locally maximally dense packings ha e igid subpackings. Ano he eason is ha solid c ys al s uc u es mus ha e some so o igidi y in o de o be s able unde ex e nal pe u ba ions. JUXTAPOSITIONS RIGIDES RE CERCLES ET DE SPH€RES PARTIE 11 : JUXTAPOSITIONS INFINIES DE MOUVEMENT FIN1 Une jux aposi ion P de ce cles dans le plan es di e n-s able pou n = 1,2, . . . si ou ensemble de n ce cles es enu ixe pa les au es. Pes des abili h inie si elle es n-s able pou ou n = 1,2, . . . Pa mi les 31 amilles de jux aposi ions egulie es connexes de ce cles dans le plan que I'on a classi iees, ce aines son de s abili e inie, d'au es non. Dans 3 des cas de amilles de judaposi ions qui ne son pas de s abili e inie, il appa ai que la plus pe i e aleu de n pou laquelle elles ne son pas n-s ables es a bi ai emen g ande, e depend d'un pa ame e de la amille. I INTRODUCTION Conside ons une jux aposi ion de ce cles dans le plan. Comme peu -on de ini ce que ep esen e la s abili e pou la jux aposi ion? Commen peu -on calcule les cas 00 cela se p esen e? Une des aisons de elles ques ions se si ue dans le esul a p incipal de la pa ie I [4]. En g os, on y a i me que les jux apo- si ions localemen maximalemen denses posseden des sous- jux aposi ions igides. Une au e aison es que les s uc u es d? 58 $? FIGURE 1 L. Fejes To h has al eady de ined a ci cle packing o be s able i each ci cle is ixed by i s neighbo s. This is pa icula ly easy o calcula e, bu in many cases i happens ha a packing is s able in his sense, bu i e en jus h ee ci cles a e allowed o mo e, he packing will “ allapa ”. Fo example, he ollowing packing, Figu el, has his p ope y. So ins ead we choose a de ini ion o s abili y which we belie e o be mo e ele an . We say a ci cle packing P, in he plane, is n-s able i e e y se o n ci cles, in P, is held ixed by he es o P. We say P is ini ely s able i P is n-s able o all n = 1, 2, . , . Thus L. Fejes To h’s de ini ion o s abili y is wha we call 1-s abili y. X The main objec o pa II is o classi y, among he 31 ypes o con- nec ed egula packings in he plane, which a e ini ely s able and which a e no . This is summa ized in Table 1 (page 65). One eason o choosing hese packings is ha since hey a e egula , hey a e a po en ial sou ce o c ys al s uc u es. A packing is egula i he e is a cong uence o he plane, aking he packing ci cles o packing ci cles, ha akes any gi en ci cle o any o he . U Ano he eason o choosing hese packings is ha hey a easou ce o in e es ing examples. In pa icula , packings numbe ed 13, 14, and 15 ha e he p ope y ha hey can be hough o as a kind o “bomb’: In each o hese examples he e is a pa ame e €I > 0 ha desc ibes a packing P,. Then he e is an in ege n(e) > 0 such ha P, is n(e)-s able bu no n(e)+l-s able. Howe e , lim n(8) = m. I we choose 8 close o 0, we can imagine mo e and mo e ci cles being allowed o mo e un il suddenly he whole packing collapses. e+o Basic o he analysis is he idea o a amewo k and he no ion o igidi y and in ini esimal igidi y as discussed in pa I. To any packing P we associa e a g aph Gp consis ing o a e ex co e- sponding o each ci cle and an edge co esponding o each pai o c is al solide doi en possede un ce ain ype de igidi e a in de demeu e s ables sous les pe u ba ions ex e nes. L. FejesTo h adejade ini une jux aposi ion s able de ce cles comme une jux aposi ion don chacun des ce cles es ixe pa ses oisins. C’es pa iculie emen simple a calcule mais, dans plusieu s cas, il appa ai qu’une jux aposi ion s able selon son sens, pou laquelle on ne pe me qu’a ois ce cles de se deplace , se (( desag ege a.. A i e d’exemple, la jux aposi ion de la igu e 1 possede ce e p o- p ie e. Ainsi, on adop e a plu B une de ini ion de s abili e qu’on c oi & e plus app op iee. On di a qu’une jux aposi ion P de ce cles, dans le plan, es n-s able si ou ensemble de n ce cles de Pes ixe pa le es e de P. On di aque Pes de s abili e inie si Pes n-s able pou ou n = 1, 2,. . . Ainsi, la s abili e elle que de inie pa L. Fejes To h co espond a ce qu’on appelle la 1-s abili k. Le p incipal bu de la pa ie II es I’iden i ica ion, pa mi les 31 ypes de jux aposi ions connexes egulie es dans le plan, de celles qui son de s abili e inie e de celles qui ne le son pas. Ceci es esume dans le ableau 1 (p. 65). Une aison qui jus i ie le choix de ces jux aposi ions es que puisqu’elles son egulie es, elles cons i uen une sou ce po en ielle de s uc u es c is allines. Une jux aposi ion es egulie e s’il exi e une isome ie du plan, aisan co espond e chaque ce cle de la jux aposi ion a un ce cle de la jux aposi ion, qui en oie ou ce cle donne su n’impo e quel au e. Une au e aison du choix de ces jux aposi ions es qu’elles son la sou ce d’exemples in e essan s. En pa iculie , les jux aposi ions de nume o 13,14 e 15 posseden la p op ie e de pou oi & e in e p e- ees comme une so e de (( bombe )). Dans chacun de ces exemples, il exis e un pa ame e 0 > 0 qui ca ac e ise une jux aposi ion Po. II exis e alo s un en ie n(e) > 0 el que P, es n(e)-s able mais n’es pas n(e)+l -s able. Tou e ois, lim n(e) = W. e-+o 59 in e sec ing ci cles. The amewo k Gp(p) associa es e ex i o pi, he cen e o ci cle i. p = (pl, . . .). I u ns ou ha he igidi y o Gp(p) is de e mined by i s in ini esimal igidi y, and hisallows us o apply many known echniques. Fo many o he 31 packings, a i s sigh , i does no seem ob ious which a e ini elys ableand which a e no . 0ne’s”physical in ui ion” can some imes be misleading. E en physical expe imen s ha e o be done ca e ully; he p ope y o he bombs migh be ha d o de ec . We belie e ha he ools p esen ed he e and in pa I a e a good i s s ep in unde s anding he igidi y o packings. We hank B anko G unbaum o poin ing ou many mis akes and making many commen s in an ea lie e sion o his pape . I CALCULA TlONS Suppose G( p) is a ini e amewo k in Euclidean space Ed as de- sc ibed in pa I, [l] o [3], bu wi h k ixed e ices, n - k a iable e ices, and e membe s, all s u s. p= (pl, . . ., p,) is he sequence o e ices o G( p). Tha is, all dis ances be ween s u endpoin s a e no allowed o dec ease. Suppose G( p) is in ini esimally igid. Since all membe s a e s u s, his can only happen i he e a e su icien ly many ixed e ices (a leas d+l), and he only i ial in ini esimal lexo G(p) is p’= 0, whe e p’= (p;, ..., pi). Thus p’= 0 is he only solu ion o he ollowing sys em o inequali- ies: (p;-p;)-(p,-pj) 2 O, o li,jlamembe o G. This is a sys em o e linea inequali ies in d(n- k) a iables, he coo dina es o he a iable e ices. This has only he ze o solu ion only i d(n-k) l I e. (2.1 1 Si on choisi 8 p es de 0, on peu imagine que de plus en plus de ce cles puissen se deplace jusqu’a ce que soudainemen la jux aposi ion en ie e s’e ond e. A la base de ce e analyse, on ou e le concep de cha pen e e les no ions de igidi e e de igidi e in ini esimale p esen es dans la pa ie I. A ou e jux aposi ion P, on associe un g aphe Gpen aisan co espond e un somme a chaque ce cle e une a e e a chaque pai e de ce cles d’in e sec ion non nulle. La cha pen e Gp(p) as- socie le somme i a p,, le cen e du ce cle i. p = (pl, . . .). II appa aT que la igidi e de Gp(p) es de e minee pa sa igidi e in ini esimale e ceci pe me d’applique plusieu s echniques connues. Plusieu s des 31 jux aposi ions ne semblen pas, a p emie e ue, pou oi B e classi iees de aqon e iden e comme e an de s abili e inie ou non. L’ccin ui ion physique)) peu pa ois indui e en e eu . MBme les expe iences physiques doi en e e ealisees a ec p e- cau ion; la p op ie e des bombes peu B e di icile a decele . Les ou ils p esen es ici e dans la pa ie I appa aissen a I’au eu comme un bon pas e s la comp ehension de la igidi e des jux aposi ions. L’au eu eme cie B anko G unbaum pou a oi signale plusieu s e eu s e a oi emis plusieu s commen ai es au suje d’une e sion p eceden e de ce a icle. I/ CALCULS Supposons que G( p) soi une cha pen e inie dans I’espace eucli- dien Ed elle qu’on I’a dec i e dans la pa ie I, dans [l] ou dans [3], mais possedan k somme s ixes, n - k somme s a iables e e memb es, ousdese ais. p= (p,, ...,p,,) es lasui edessomme s de G(p). Ainsi, aucune dis ance en e les ex e ni es d’un e ai ne peu dec oi e. Supposons que G( p) soi in ini esimalemen ig ide. Puisque ous 60 I is help ul o ew i e (2.1) in e ms o he a e age deg ee o a e ex 7 whe e - i , V=C- , is he deg ee o he i- h a iable e ex in G. A e ex has deg ee i i is a e ex o exac ly edges (also called membe s). i (n-k) ’ Suppose ha each ixed e exo G isonexac lyoneedgeo G. Then he numbe o e ex-edge incidences is 2e = (C ,) + k, whe e he sum is o e a iable e ices as be o e. Thus 2e = (n- k) V+ k. (2.2) Combining his wi h (2.1) we ge d(n-k)+1 I ‘/Z[(n-k) +k], 2d-(%)s V La e in ou applica ions o packings i will u n ou ha k will be much smalle han n, and so will hen be no much smalle han 2 d. ses memb es son des e ais, ceci ne peu se p odui e que s’il y a un nomb e su isammen g and de somme s ixes (au moins d+l); le seul mou emen in ini esimal de G(p) es p’= 0,oU p‘= ( p;, . . ., p;). Ainsi p’= 0 es la seule solu ion du sys eme d’inequa ions sui an : (p; - pi). (pi- pj) 2 0, pou {i, jl memb e de G. C’es un sys eme de e inequa ions lineai es en d(n- k) a iables, les coo donnees des somme s a iables. II ne possede que la solu- ion nulle seulemen si d(n-k) 1 2 e. (2.1 1 II es u ile de eec i e (2.1) en onc ion du deg 6 moyen d’un som- me V, oh - i , V=S- I (n-k) OD , es le deg e du i-e ne somme a iable de G. Un somme es de deg e s’il es le somme d’exac emen a e es (memb es). Supposons que chaque somme ixe de G soi su exac emen une a Q e de G. Alo s le nomb e d’incidences somme -a 8 e es 2e = (C i)+k, OD la somme pa cou les somme s a iables comme p ecedem- men . Ainsi 2e = (n- k) V+ k. (2.2) En combinan ce esul a a ec (2.1), on ob ien d(n-k)+l 2 Vz[(n-k)V+k], 2d-(S)s V (2.3) Plus loin dans les applica ions aux jux aposi ions, il appa ai a que k es beaucoup plus pe i que n, e ainsi ne se a pas beaucoup plus pe i que 2d. 61 Ill GRAM WITHSM AVERAGE DEGREE We can use he calcula ions o sec ion II o elimina e as being igid many g aphs wi h low a e age deg ee 7. Theo em 3.7 Le G(p) be a connec ed (in ini esimal&) igid s u g aph in Ed whe e each a iable e ex o G has deg ee d + 1, and each ixed e ex has deg ee 1. Then G is a ee. 1.e. he e a e no cycles in G. P oo Using he no a ion abo e, 7 = d+l. Then (2.2) implies, 2(n- e) = 2n- (n- k) (d 1) - k = 2n- (n- k) d-n+ k- k (3.1 1 = n-(n-k)d. On he o he hand, since G( p) is igid, using (2.3) and 7 = d 1, we ge 2d- (x) k- 2 2 d+l , which simpli ies o 2 I n-d(n-k). Combining (3.1) and (3.2) we ge 2 I 2(n-e) o 1 5 n-e. Since G is connec ed, his implies G is a ee. 111 GRAPHES DE PETIT DEGREMOYEAT En u ilisan les calculs de la sec ion II, il es passible d’elimine plusieu s g aphes de pe i deg e moyen 7, ceux-ci e an igides. Theo 4me 3.7 Soi G( p) un g aphe d’e ais connexe (in ini hima- lemen ) igide dans Ed, 00 chaque somme a iable de G es de deg e d + 1 e chaque somme ixe es de deg 6 1. Alon G es un a b e. C’es -a-di e qu’il n’y a aucun cycle dans G. Ddmons a ion A ec la no a ion in odui e p ecedemmen , on a = d + 1. Alo s, (2.2) implique - 2(n- e) = 2n- (n- k) (d 1) - k = 2n- (n- k) d- n+ k- k = n-(n-k)d. (3.1) D’au e pa , puisque G(p) es igide, en in oquan (2.3) e le ai que 7 = d +1, on ob ien ce qu’on peu simpli ie de la acon sui an e: 2 I n-d(n-k). En combinan (3.1) e (3.2), on ob ien 2 5 2(n-e) ou 1 I n-e. Puisque G es connexe, ceci implique que G es un a b e. (3.2) 62 FIGURE 2 In he plane E2 his says ha i he deg ee o each a iable e ex is 3, hen he e can be no cycles i G(p) is o be igid. Fo example, he s u amewo k (Figu e 2) is no igid. Va iable e ices a e deno ed by 0, ixed e ices by 0, and ep esen a s u . No e ha in he abo e, he e is no eal loss o gene ali y in assuming ha he deg ee o each ixed e ex is 1. We can c ea e a ixed e ex o each edge ha has some ixed e ex on i and ega d each o hese new ixed e ices as dis inc in G bu wi h he same posi ion ec o s pi in he amewo k G(p). o FIGURE 3 Al e na i ely, suppose i is a ixed e ex o G, j is a a iable e ex, and (i, j} is an edge o G. Then we can eplace Ii, 11 wi h Ii: j} whe e i’ is ano he ixed e ex and pu p,. anywhe e on he ay om p, o pi in Ed, o ge a new g aph and a new amewo k ha is in ini esi- mally igid i and only i he o iginal g aph G(p) is. See Figu e 3. Y w wi h es is eplaced e nplack JI We can do he abo e p ocess o each Ii, jl membe in G o all j and hen elimina e i. The e is also a con e se o Theo em 3.1. Namely i each a iable e exo G(p) isin he in e io o hecon exhullo i sd l neighbo s, he endpoin s o G a e he ixed e ices, and G is a ee, hen G(p) is in ini esimally igid. We omi he p oo . Dans le plan E2, ce esul a a i me que si le deg e de chaque som- me a iable es egal a 3, alo s il ne peu y a oi aucun cycle si G(p) doi i e igide. Pa exemple, la cha pen e d’e ais de laligu e 2 n’es pas igide. Les somme s a iables son designes pa 0, les som- me s ixes pa ., e ou I ep esen e un e ai. On no e que dans ce qui p edde, il n’y a pas de e i able pe e de gene ali i en supposan que le deg e de chaque somme ixe es egal a 1. On peu c ee un somme ixe pou chaquea h e possedan au moins un somme ixe e in e p e e chacun de ces nou eaux somme s ixes comme des somme s dis inc s dans G en conse - an ou e ois les mhmes ec eu s de posi ion pi dans la cha pen e G( P)- Comme al e na i e, supposons que i soi un somme ixe de G, j un somme a iable e Ii,jl une a h e de G. On peu alo s emplace {iJ pa (i;j}, oh i’es un au e somme ixe e pi. es place n’impo e oh su le ayon qui a de p, a pi dans Ed. On ob ien un nou eau g aphe e une nou elle cha pen e qui es in ini esimalemen igide si e seulemen si le g aphe o iginal G(p) I’es aussi. Voi la igu e 3. Ce p ocessus peu & e e ec ue su chaque memb e (i, jl de G pou ou j e on elimine ainsi i. II exis e une ecip oque au heo eme 3.1, En e e , si chaque som- me a iable de G(p) se si ue a I’in e ieu de I’en eloppe con exe de ses d+l oisins, que les ex emi es de G son les somme s ixes e que G es un a b e, alo s G(p) es in ini esimalemen igide. On ome a la demons a ion. 63 IV THE 31 TYPES OF CIRCLE PACKINGS In he ollowing we shall show ep esen a i es o he 31 ypes o egula connec ed ci cle packings in he plane. These a e aken om he booko L. FejesTo h [6], bu we ha echosenadi e en o de ing so ha ela ed packings a e nea o each o he . See also G iinbaum and Shepha d [7] o a desc ip ion o he classi ica ion. In each diag am (Figu e 4, pages 66-70) we i s show he packing wi h he g aph o he packing indica ed as well. On his diag am we ha e indica ed a igid o de ing, i i exis s, assuming he bounda y e ices a e ixed. Tha is, by adding in he e ices o he associa ed od amewo k o he ixed e ices in he o de indica ed, we ge successi ely amewo ks ha a e in ini esimally igid. Each o he new e ices mus be joined o a leas wo p e ious e ices such ha all h ee do no lie on a s aigh line. See Lemma 6.2 o pa I [4, p.51 I. Di ec ly beside each o he 31 packings, we ha e indica ed a ecip- ocal diag am, i i exis s. He e each polygon o he ecip ocal dia- g am co esponds o a e ex in he g aph o he packing abo e i , and co esponding edges a e pe pendicula . I he e isa igid o de - ing and a ecip ocal s ess diag am, he o de ing is also indica ed in he s ess diag am. S ess diag ams a e discussed in sec ion VII o pa I [4, p.521. By a heo em o Ro h and Whi eley [8] (see heo em 6.1 o pa I [4]), we know ha he amewo k o a packing G,(p) has bo h he associa ed od amewo k G,(p) in ini esimally igid and a ecip o- cal s ess diag am i and only i G,(p) is in ini esimally igid. Thus i he e is a igid o de ing and he s ess exis s o a bi a ily la ge subpackings, hen we know ha he packing is ini ely s able. I he e is no igid o de ing, G,(p) may s ill be in ini esimally igid, bu o each o ou cases, when he e is no igid o de ing, G,(p) will IV LES 31 NPES RE JUXTAPOSlTlOlys RE CERCLES Dans ce qui sui , on e a des ep esen an s des 31 ypes de jux aposi ions egulie es connexes de ce cles dans le plan. IIs son ex ai s du li e de L. Fejes To h [6] ; on a ou e ois choisi un o d e di e en , de elle so e que les jux aposi ions appa en ees soien p oches les unes des au es. On peu consul e aussi G iinbaum & Shepha d [7] pou une desc ip ion de la classi ica ion. Dans chaque diag amme ( igu e 4, pages 66 a 70), on mon e ou d’abo d la jux aposi ion acco npagnee de I’indica ion de son g aphe. Su chaque diag amme, on a iden i ie un o d e igide, si un el o d e exis e, en supposan que les somme s de la on ie e son ixes. En e e , en ajou an les somme s de la cha pen e de ba es associbe aux somme s ixes dans I’o d e indique, on ob iend a successi e- men des cha pen es in ini esimalemen igides. Chaque nou eau somme doi & e lie a au moins deux somme s deja exis an s de elle manie e qu’ils ne soien pas ous les ois colineai es. Voi le lemme 6.2 de la pa ie I [4, p.521. Di ec emen ad oi e de chacune des 31 jux aposi ions, on a indiqub un diag amme bcip oque, s’il en exis e. Ici, chaque polygone du diag amme ecip oque co espond a un somme dans le g aphe de la jux aposi ion qui se si ue a cB e de Iui, e les a e es co espon- dan es son pe pendiculai es. Si un o d e igide e un diag amme ecip oque de con ain e exis en , I’o d e es aussi indique dans le diag amme de con ain e. Les diag ammes de con ain e son ai- es dans la sec ion VII de la pa ie l [4, p.521. Selon un heo eme de Ro h e Whi eley [8] ( oi le heo eme 6.1 de la pa ie I [4]), on sai que la cha pen e d’une jux aposi ion Gp(p) possede a la ois une cha pen e de ba es associee c,(p) in ini e- simalemen igide e un diag amme de con ain e ecip oque si e seulemen si G,(p) es in ini esimalemen igide. Ainsi, s’il y a un o d e igide e que la con ain e exis e pou des sous-jux aposi ions 64 no be in ini esimally igid. He e o cou se all bu a ini e numbe o he e ices a e ixed. Simila ly, o he cases o hose packings (1 o 16, Figu e 4) whe e no ecip ocal s ess diag am is gi en, we will show ha i in ac does no exis . Thus by Ro h and Whi eley in ei he case, some Cp(p) is no in i- ni esimally igid o he s ess diag am does no exis , P is no ini ely s able. Fo packings 17 and 18 (Figu e 4) we will show di ec ly ha cp(p) is no in ini esimally igid by exhibi ing a non- i ial in ini esimal lex p’. In case he deg ee o each e ex o G,is 3, we know om Theo em 3.1 ha i we ake any cycle in Gp hen he amewo k wi h jus ha cycle as he a iable e ices is no in ini esimally igid. Thus P is ne e ini ely s able in case each ci cle ouches jus 3 o he s, since he eisalwaysacycleinsuchg aphs.Thisshowspackings19 o31 (Figu e 4) a e no ini ely s able. In case each o he egions de ined by G,(p) is a egula polygon, a ecip ocal diag am always exis s by joining he cen e s o adjacen egula polygons. In he diag am we ha e chosen he mos “ egula ” ecip ocal, al- hough any ep esen a i e would do. In each o he cases when a ecip ocal exis s we expec ha he gene al cons uc ion should be clea . In he cases when he ecip ocal does no exis , we lea e ha pa o he pic u e blank. In all o he cases (al hough i does no seem o ollow om a gene al heo em) i u ns ou ha i a ecip o- cal exis s o e e y ini e po ion o he packing, an in ini e ecip ocal diag am exis s o he whole packing. We ha e chosen o show his diag am, e en i each ini e diag am could be made mo e egula . a bi ai emen g andes, alo s on sai que la jux aposi ion es de s abili e inie. S’il n’y a pas d’o d e igide, cp(p) peu enco e & e in ini esimale- men igide; mais pou les cas conside es ici, lo squ’il n’y au a pas d’o d e igide, Gp(p) ne se a pas in ini esimalemen igide. Ici, e i- demmen , ous les somme s sau un nomb e ini son ixes. De mime, en ce qui conce ne les cas des jux aposi ions 1 a 16 ( igu e 4) pou lesquelles on ne donne pas de diag amme de con- ain e ecip oque, on mon e a qu’en ai il n’en n’exis e pas. Ainsi, pa Ro h e Whi eley dans les deux cas, que ce soi pa ce que G,(p) n’es pas in ini esimalemen igide ou pa ce qu’il n’exis e pas de diag amme de con ain e, P n’es pas de s abili e inie. Pou les jux aposi ions 17 e 18 ( igu e 4), on mon e a di ec emen que Gp(p) n’es pas in ini esimalemen igide en exhiban une de- o ma ion in ini esimale non i iale p’. Si le deg e de chaque somme de Gp es egal a 3, on sai pa le heo eme 3.1 que pou ou cycle dans G,, la cha pen e n’ayan que les somme s de ce cycle comme somme s a iables n’es pas in ini esimalemen igide. Ainsi, P n’es pas de s abili e inie si cha- que ce cle n’en ouche que 3 au es, puisqu’il y a oujou s un cycle dans de els g aphes. Ceci demon e que les jux aposi ions 19 a 31 ( igu e 4) ne son pas de s abili e inie. Si chacune des egions de inies pa G,(p) es un polygone egulie , il exis e oujou s un diag amme ecip oque cons ui en joignan les cen es des polygones egulie s adjacen s. Dans le diag amme, on a choisi la ecip oque la plus (( egulie e )), meme si ou ep esen an au ai ai I’a ai e. Dans chacun des cas 00 une ecip oque exis e, on espe e que la cons uc ion gene ale es Clai e. Lo squ’il n’exis ai pas de ecip oque, on a laisse en blanc ce e pa ie de la igu e. Dans ous les cas, (mime si ce ne semble pas decoule d’un heo eme gene al) il appa ai que si une ecip o- que exis e pou ou e pa ie inie de la jux aposi ion, il exis e un 65 FIGURE 4 Pages 66 o 70. D awings/Dessins: Richa d Geo ion. TABLE 1 / TABLEAU 1 The in o ma ion is summa ized in Table 1, whe e we ha e also in- cluded he in o ma ion abou whe he he packing is 1-s able. O cou se, many o he packings indica ed by he pic u es a e jus one packing in a amily o packings, bu i happens o u n ou ha o each case, o ini e s abili y, i one o hese packings is ini ely s able, all membe s a e. I a gi en amily o packings is no ini ely s able, we indica e an in ege n, whe e he packings a e no n-s able. Howe e , o h ee amilies o packings 13, 14, and 16, such an n depends on which membe o he amily is being conside ed, and as a ce ain pa am- e e changes, hisn can bea bi a ilyla ge. 1.e. heya e he"bombs" as men ioned in he in oduc ion. This is indica ed by 00 in he able. Fo he case o 1-s abili y we indica e by an 'S' he si ua ion whe e some o he packings in he gi en amily a e 1-s able, and some a e no 1 -s able. Fo he whole able, 'A indica es ha he condi ion always holds, and 'N' indica es ha i ne e holds. diag amme ecip oque in ini pou la jux aposi ion en en ie . Les choixon e e ealises en onc ion de ce diag amme, m6me si chaque diag amme ini au ai pu & e plus kgulie . Le ableau 1 con ien un esume de ce e in o ma ion ; on y indique aussi si la jux aposi ion es 1-s able. E ide nmen , plusieu s jux aposi ions illus ees ne son qu'une jux aposi ion pa ni une amille de jux aposi ions ; mais il appa ai que dans chacun de ces cas, en ce qui conce ne la s abili e inie, si I'une des jux aposi ions d'une amille possede ce e p op ie e, ous les memb es de ce e amille la posseden . Lo squ'une ce aine amille de jux aposi ions n'es pas de s abili e inie, on I'indique pa un en ie n el que les jux aposi ions de ce e a nille ne son pas n-s ables. Tou e ois, pou ois amilles de jux aposi ions, celles qui po en les nume os 13, 14 e 16, un el n depend du memb e de la amille conside e, e selon les a ia ions d'un ce ain pa ame e, ce n peu i e a bi ai e nen g and. II s'agi des (( bombes )) men ionnees dans I'in oduc ion. Dans le ableau, on indique pa 00 une elle si ua ion. Pou ce qui es de la 1-s abili e, un 'S' indique que ce laines jux a- posi ions de la amille en ques ion son 1 -s able, e ce aines ne le son pas. Pou I'ensemble du ableau, 'A indique que la p op ie e es oujou s alide, e 'N' indique qu'elle ne I'es jamais. Rod amewo k is in ini esimally igid Rigidi k in ini ksimale / cha pen e de ba es AAAAAAAAAAAAAAAANNNNNNNNNNNNNNW Recip ocal exis s Exis ence de la kcip oque Packing is ini ely s able S abili b inie de la jux aDosi ion Packing Is 1-s able 1-s abili .4 de la jux aposi ion AAAAAAAAAAAANNAAANAAANNAANNAANN A A A A A A A A A A A A N- N- A N- N18 Nl8 N6 N6 N6 N6 N6 N4 N4 N4 N4 N4 N3 N3 N3 AAAAAAAAAAAAAAAAAAAAAAAAAASAASS 72 FIGURE 7 Decompose he lines o he ecip ocal in o wo o e lapping hexago- nal " ilings" as in Figu e 7. The only equi emen o he ecip ocal is ha he wo hexagonal ilings o e lap a he indica ed e ices and ha he angles o each iling, sepa a ely a e e y pai o in e sec ing edges, be 120". The / I wo ilings will be il ed ( o packing numbe 16) a some angle 9 < 60". O cou se, he hexagonal iles need no be egula . We now look a one hexagonal ile wi h he leng hs o he sides as indica ed in Figu e 8. The do ed lines (.....) a e pa allel o he co esponding b oken lines (-----) o he hexagonal iling, and a e he e o e e ence. FIGURE a w5 Lemma 5.1 w,/w, 1 k, > 1 and 03/01 5 k, > 0, whe e k, and k, I ; a e unc ions o 9 only. - - - - - - - - - - -.- - I ' : '. P oo Fo w1/w4 , look a Figu e 9 nea he 0 e ex. . c.. . ...I.... (60'-2 .. .. {/ ; By he law o sines I . Le k, = (-) sin 120" = (-) sin 60" > sin 9 sin 8 -- I is clea ha w, > w, , o4 > a,. Thus On decompose les segmen s de d oi e de la ecip oque en deux (( pa ages )) hexagonaux se che auchan , comme A la igu e 7. Les seules exigences pou la ecip oque es que les deux pa ages hexagonaux se che auchen aux somme s indiques e que, pou chaque pa age sepa emen , I'angle en ou e pai e d'a 4 es se cou- pan soien de 120". Pou la jux aposi ion 16, les deux jux aposi ions bascule on a un ce ain angle 9 < 60". E idemmen , les pa es hexagonaux ne son pas necessai emen egulie s. Conside ons un pa e hexagonal de cB es de longueu s elles qu'indiqueesa la igu e 8. Les lignes poin illees (..-.) son pa allbles aux lignes b isees (-----) co espondan es dans le pa age hexa- gonal ; on les indique a i e de e e ence. Lemme 5.1 a,/w, 2 k, > 1 e 03/w1 5 k, > 0, 00 k, e k, son onc ions de 9 unigue nen . Dhons a ion Pou w,/w, , on examine la igu e 9 p es du somme 0. Pa la Ioi des sinus - - x- -~ 01 -=- X 04 sin 9 sin 120" ' sin 120" sin 9 w,=x- - sin 120" - sin 120" sin 9 Soi k, = (-) sin 120" = (-) sin 60" > sin 8 sin 8 - =k,>l. w4 04 -- II es clai que a, > o, , o, > a,. Ainsi - - >3 = k, >l. 04 04 73 FIGURE g / / 120" ** ........... .- 120" ,120" To ge he o he inequali y look a he lowe igh hand quad ila e al (Flgu e 10). - 03 = X sin 120" sin(60 -0) sin 120" sin (60"- 0) 03 < a, = x =a, - ... sin 9 sin 120" sin 120" sin 120" sin(60"- 0) < sin(60"-0) 0 Le k2 = sin ; hen 3 I k, , sin (60"- 9) 01 We con inue o look o a con adic ion. F om Figu e 8 we can shi he indices by 2 and apply Lemma 5.1 in each case. We ge 03/o, I k*, 05/03 I k,, w1/w5 I k, 04/w1 I Ilk, < 1, os/03 I llk, < 1, 02/05 I Ilk, < 1 , Combining we ge Fo he inal con adic ion, suppose we ha e a chain o hexagons as abo e, bu sa is ying he abo e inequali ies on hei edge leng hs. No e ha he di ec ions o inc easing and dec easing leng hs a e always hesame,and inou si ua ion heya eas ollowsin Figu ell. Thus one can ind a bi a ily long chains o hexagons in he shape o a closed iangle wi h only 3 changes in di ec ion, as in Figu e 12. A in d'ob eni I'au e inegali e, on obse e le quad ila e e se ou an en bas e a d oi e ( igu e 10). - 03 = X sin 120" sin(60 - 0) sin 120" o3 < G3 = x sin(60"- 0) - sin 9 sin 120" sin 120" - - 0,. ~. < sin(60"- 0) sin 120" sin (60"- 0) 0 Soi k2 = Sin ' ; alo s 3 I k, sin(60"- 9) 01 On che che oujou s une con adic ion. On peu , dans la igu e 8, deplace de 2 les indices e applique le lemme 5.1 dans chaque cas. On ob ien 03/01 I k, , 05/03 I k, , w1/05 I k, 04/w1 I l/k, < 1, 06/W3 I l/k, < 1, o*/w5 I l/k, < 1 . En combinan ces esul a s. on ob ien A in d'ob eni la con adic ion inale, on suppose que I'on a une chaine d'hexagones comme ci-dews e don les longueu s d'a g- es sa is on les inegali es p eceden es. On no e que les di ec ions de c oissance e de dec oissance des longueu s son oujou s les m&nes e , dans la si ua ion qui nous occupe, elles son elles que p esen ees dans la igu e 11. Ainsi, il es possible de ou e des chaines d'hexagones a bi ai- emen longues qui se p esen en sous la o me d'un iangle e me possedan seulemen 3 changemen s de di ec ion ( igu e 12). 74 FIGURE 12 Suppose one p oceeds n s eps on each side o he iangle o hexa- gons. I we label he leng hs o he sides indica ed by !, , . . ., esn, hen Bu his is impossible since k, > 1, i n is chosen la ge enough. Thus packing numbe 16 has no ecip ocal diag am i he numbe o packing elemen s o which i co esponds is la ge enough. Thus packing 16 is no ini ely s able. Packings 17and 18 Fo bo h packings G,(p) is no in ini esimally igid. We indica e he in ini esimal mo ion in Figu e 13. Only he 18 e ices o he wo inne ings mo e. Fo packing 18 he e is no ecip ocal diag am ei he , i one akes a la ge enough po ion o he packing. As in cases o packings 13,14 and 16 as he hombus becomes mo e squa e, la ge pa s o he packing ha e a ecip ocal diag am. Packing 4 In acco dance wi h ou policy o choosing he mos egula ecip o- cal possible, we ha e chosen a iling by cong uen polygons. See he a icles o D. Scha schneide [9] o J.A. Dunn [5]. Gi en ou ex a condi ions and ha he iling is o be wi h cong uen iles, we a e o ced o choose he iling shown. Packings 2,3,5 and 6 gi e o he well-known ilings by cong uen pen agons. Packings 18,22,23,26,30 and 31 Fo hese packings he e is no ecip ocal diag am, bu his is no needed o show ha hey a e no ini ely s able. Special a gumen s (which a e omi ed) handle each o hese cases. Supposons que I’on e ec ue n e apes su chaque co e du iangle d’hexagones. Si on e ique e les longueu s desa d es pa , ,. . ., la”, alo s Mais ceci es impossible puisque, si n a e e choisi su isammen g and, k, > 1. Ainsi, la jux aposi ion nume o 16 ne possede pas de diag amme ecip oque si le nomb e d’elemen s de jux aposi ion qui lui co espond es su isammen g and. La jux aposi ion 16 n’es donc pas de s abili e inie. Jux aposi ions 17 e 18 Pou ces deux jux aposi ions, G,(p) n’es pas in ini esimalemen igide. La igu e 13 illus e le mou emen in ini esimal. Ce ne son que les 18 somme s des deux anneaux in e ieu s qui se deplacen . De plus, la jux aposi ion 18 ne possede pas de diag amme eci- p oque lo squ’on choisi une pa ie su isammen g ande de la jux aposi ion. Comme dans les cas des jux aposi ions 13,14 e 16, lo sque les losanges de iennen plus ca es, de plus g andes pa - ies de la jux aposi ion posseden un diag amme ecip oque. Jux aposi ion 4 En acco d a ec le p incipe du choix de la ecip oque la plus egu- lie e, on a choisi un pa age cons i ue de polygones cong uen s. On peu consul e a ce suje les a icles de D. Scha schneide [9] ou J.A. Dunn [5]. E an donne les condi ions supplemen ai es qu’on impose e le ai que le pa age doi d e cons i ue de pa es cong u- en s, le pa age illus e es le seul choix. Les jux aposi ions 2,3, 5 e 6 p esen en d’au es pa ages bien connus, cons i ues ceux-la de pen agones cong uen s. 75 Packinos 13, 14 and 16 The e a e he “bombs” men ioned in he in oduc ion. These ami- lies o packings ha e as limi s packing 8, o packings 13 and 14; and packing 15, o packing 16.The limi packings ha ea ecip ocal, and cp(p) is in ini esimally igid o he limi packings (whe eall bu a ini e numbe o he e ices a e ixed). Fo a ixed ini e po ion o G,, he e a e a ini e numbe o inequali ies ha de e mine he in ini esimal igidi yo G, (p) (in a ini edimensional Euclidean space o in ini esimal de o ma ions), as in sec ion II (o sec ion 111 o pa I [4]). Then any su icien ly small pe u ba ion o he inequali- ies does no c ea e a non-ze o solu ion. Thus as P app oaches i s limi , a bi a ily la ge se s o e ices mus be allowed o be a iable, in o de o P no o be ini ely s able. Thus since c,(p) is always in ini esimally igid in hese examples, he ecip ocal diag am exis s o a bi a ily la ge po ions o G, (p), as P app oaches i s limi . .11111. Jux aposi ions 18,22,23,26, 30 e 31 Ces jux aposi ions ne posseden pas de diag a nmes ecip oques, mais il n’es pas necessai e de mon e qu’elles ne son pas de s abili e inie. On peu ai e chacun de ces cas a I’aide d’a gumen s pa iculie s (que I’on ome a). Jux aposi ions 13, 14 e 16 Ce son les (( bombes )) deja men ionnees en in oduc ion. Ces a- milles de jux aposi ions on comme limi es la jux aposi ion 8, en ce qui conce ne les jux aposi ions 13 e 14; e la jux aposi ion 15, pou la jux aposi ion 16. Les jux aposi ions limi es posseden des eci- p oques, e G, (p) es in ini esimalemen igide pou les jux aposi- ions limi es (oa ous les somme s sau un nomb e ini son ixes). Pou une pa ie inie ixee de G,, il exis e un nomb e ini d’inegali es qui de e minen la igidi 6 in ini himale de Gp(p) (dans un espace euclidien de dimension ini de de o ma ions in ini esimales), comme alasec ion II (ou lasec ion Ill de la pa ie I).Alo s, ou e pe u ba ion su isammen pe i e des inegali es n’en aine pas une solu ion non nulle. Ainsi, lo sque P s’app oche de sa limi e, des ensembles a - bi ai emen g ands de somme s peu en & e a iable, a in que P ne soi pas de s abili e inie. Ainsi, puisque G,(p) es oujou s in ini esimalemen igide dans ces exemples, le diag amme eci- p oque exis e pou des pa ies a bi ai emen g andes de G, (p), lo sque P end e s sa limi e. .11111. 76 BlBuoGRA PH Y [l] L. Asimow and B. Ro h “Tha lgldl y o g aphs.” T ans. A ne . Ma h. SOC. 245 (1975), An in oduc ion o he basic heo y o p.279-289. igidi y. Une in oduc ion B la heo ie ondamen- ale de la igidi e. [2] L. Asimow and B. Ro h “The lgldl y o g aphs 11.” J. Ma h. Appl. 68 (1979), p.171-190. A con inua ion o Pa 1. La sui e de la pa ie 1. [3] Robe Connelly “The lgldl y o ce ain cabled amewo ks and he second o de lgldl y o a bi a ily langula ed con ex su iace .” Ad ances in Ma h. 37, N0.3 (1980), The i le is he abs ac . Le i e en es un esumd. p.272-299. [I] Robe Connelly “Rlgld ci cla and sphe a packlngs. Pa I: Flnl e packing%” S uc u al Topology, 14 (1988), p.43-60. The basic gene al heo y used o he igidi y o packings. La hlo ie gene aale de base u ilisee dans la igidi e des jux aposi ions. [5] J.A. Dunn “Tessella ions wl h pen qons.” Ma hema ical Gase e, 55, Dec. 1971, p.366-369. Follow-up co espondence Fxamples o ilings wi h pen agons. Fxemples de pa ages d I‘aide de pen ag ones. V01.56, p.332-335. [6] L. Fejes T6 h Regula Flgum. Pe ga non P ess (1964). An in oduc ion o many ideas ela ed o packing and co e ing p oblems. Une in oduc ion B plusieu s idees Wes aux p oblimes de jux aposi ion e de ecou emen . [7] B anko G unbaum and G.C. Shepha d “A hle a chy o classl lca lon ma hods o pa e ns.” Zei sch i u K is allog aphie, 154 A ca e ul discussion o he me hod o classi ica ion o egula packings. Une discussion soignee de la me hode de classi ica ion des jux aposi ions eguli& es. (1 981 ), p.163-I 87. [8] B. Ro h and W. Whi eley “lenseg i y amewo ks.” T ans. o A.M.S. (1981), p.410-446. The basics o s a ics and in ini esimal igidi y o amewo ks wi h cables and s u s. Les ondemen s de la igidi d s a ique e de la igidi e in ini esimaie des cha pen es de cables e d’e ais. [8] Do is Scha schneide “llllng he plane wl h cong uen pen agons.” Ma h. Mag., Vo1.51, No.1, Jan.1978, p.29- 44. Mo e examples o ilings o he plane wi h cong uen pen agons. Enco e des exemples de pa ages du plan B I’aide de pen agones cong uen s.