Hét, páronként érintkezo˝ végtelen henger Bozóki Sándor1,2 , Rónyai Lajos1,3 , Tsung-Lin Lee4 1 2 3
MTA SZTAKI
Budapesti Corvinus Egyetem
Budapesti Muszaki ˝ és Gazdaságtudományi Egyetem 4
National Sun Yat-sen University, Tajvan 2015. március 30. – p. 1/43
Páronként érintkezo˝ érmék
forrás: Dudeney: Amusements in mathematics (1917), 143. o. – p. 2/43
Páronként érintkezo˝ érmék
forrás: Dudeney: Amusements in mathematics (1917), 248. o. – p. 3/43
Páronként érintkezo˝ cigaretták
forrás: Grätzer József: Rébusz (1935), 115. o. – p. 4/43
Páronként érintkezo˝ cigaretták
forrás: Grätzer József: Rébusz (1935), 233. o. – p. 5/43
Páronként érintkezo˝ cigaretták Martin Gardner az 50-es évek végén a Scientific American hasábjain tuzte ˝ ki a feladatot. Meglepetésére nemcsak 6, de 7 cigarettás megoldás is beérkezett.
– p. 6/43
Páronként érintkezo˝ cigaretták Martin Gardner az 50-es évek végén a Scientific American hasábjain tuzte ˝ ki a feladatot. Meglepetésére nemcsak 6, de 7 cigarettás megoldás is beérkezett.
forrás: Gardner (1959), √ 115. o. (feltétel: hossz/átméro˝ ≥ 7 3/2 ≈ 6.06.)
– p. 7/43
Littlewood sejtése El lehet-e helyezni a térben hét, azonos sugarú, páronként ˝ végtelen hosszú hengert? érintkezo, “Is it possible in 3-space for seven infinite circular cylinders of unit radius each to touch all the others? Seven is the number suggested by constants.” (Littlewood, 1968, 20. o.)
A páronként érintkezo˝ végtelen hosszú hengerek maximális száma megegyezik azon egyenesek maximális számával, amelyek páronként azonos pozitív távolságra vannak egymástól. Littlewood sejtésének ekvivalens átfogalmazása: Létezik-e hét, egymástól azonos pozitív távolságra lévo˝ térbeli egyenes?
– p. 8/43
Littlewood sejtése El lehet-e helyezni a térben hét, azonos sugarú, páronként ˝ végtelen hosszú hengert? érintkezo, “Is it possible in 3-space for seven infinite circular cylinders of unit radius each to touch all the others? Seven is the number suggested by constants.” (Littlewood, 1968, 20. o.)
Az eddig talált források közül Ogilvy (1962) könyve a legkorábbi, amelyben szerepel Littlewood sejtése: „How many lines can be drawn in 3-space, each a unit distant from every one of the others? It is conjectured that seven is the maximum number, but no proof is available. Seven might be too high or too low.” (61. o.) „The question on skew lines in 3-space was suggested by Littlewood.” (153. o.) – p. 9/43
6 végtelen henger
forrás: Brass, Moser, Pach (2005), 98. o. – p. 10/43
Kuperberg javaslata 8 végtelen hengerre
forrás: Bezdek, Ambrus (2008), 1804. o. Bezdek András és Ambrus Gergely 2008-ban bebizonyította, hogy Kuperberg ezen konstrukciója nem jó, azaz legalább egy hengerpár nem érintkezik. – p. 11/43
Az eddig ismert legjobb korlátok
˝ végtelen Tétel (Bezdek, 2005): A páronként érintkezo, hosszú, azonos sugarú hengerek maximális száma legfeljebb 24.
˝ végtelen hosszú, azonos sugarú A páronként érintkezo, hengerek maximális száma legalább 6, de legfeljebb 24.
– p. 12/43
˝ Az eloadás további részében a Bozóki, S., Lee, T.L., Rónyai, L. (2015): Seven mutually touching infinite cylinders, Computational Geometry: Theory and Applications, 48(2):87–93. cikk eredményeit foglaljuk össze: Megmutatjuk, hogy az alsó korlát 7-re javítható, mivel sikerült találni 7 hengeres elrendezés(eke)t.
– p. 13/43
A modell
Rögzítsük a hengerek sugarát 1-re, vagyis az egyenesek távolságát 2-re. A Pi ponton áthaladó wi irányvektorú egyenes paraméteres egyenlete: ℓi (s) = Pi + s wi ,
s ∈ R.
˝ akkor a távolságuk felírható Ha ℓi és ℓj kitéro, −−−→ |(Pi Pj ) · (wi × wj )| d(ℓi , ℓj ) = ||wi × wj ||
alakban.
– p. 14/43
A modell d = 2-vel és átrendezés után kapjuk: 2 −−−→ |(Pi Pj ) · (wi × wj )| − 4||wi × wj ||2 = 0.
Legyen Pi = (xi , yi , zi ), wi = (ti , ui , vi ). A vegyesszorzat determinánsos alakját felírva adódik:
2
xj − xi yj − yi zj − zi det ti ui vi − 4 (ui vj − vi uj )2 + tj uj vj 2 2 + (vi tj − ti vj ) + (ti uj − ui tj ) = 0.
Az egyenlet bal oldalát kifejtve egy 12 változós, 6-od fokú polinomot kapunk, amely 84 monóm lineáris kombinációja. – p. 15/43
A változók számának csökkentése
Feltehetjük, hogy az ℓ1 egyenes átmegy a P1 (0, 0, −1) ponton és az irányvektora w1 = (1, 0, 0). Szintén rögzíthetjük az elso˝ két henger érintési pontját – vagyis az elso˝ ˝ két egyenes távolságát realizáló szakasz felezopontját –, ˝ adódik P2 (0, 0, 1), ℓ2 irányát pedig legyen ez az origó. Ebbol már egyetlen változóval jellemezni tudjuk. Az elso˝ két egyenest eredetileg leíró 12 változó helyett elegendo˝ 1. ˝ hogy az Az általánosság megszorítása nélkül felteheto, ℓi (i = 3, . . . , 7) egyenesek egyike sem vízszintes, ezért metszik a z = 0 síkot: zi = 0 (i = 3, . . . , 7).
– p. 16/43
A változók számának csökkentése
Végül az egyenesek irányvektorának hosszára a ti + ui + vi = 1 (i = 3, . . . , 7) feltétellel élünk. Ez ugyan kizárja a ti + ui + vi = 0 egyenletet teljesíto˝ irányvektorokat, ˝ nem az összes megoldást keressük, de mivel egyelore hanem legalább egy megoldást, látni fogjuk, hogy az ily módon szukített ˝ keresési térben is találunk gyököt. A redukció eredménye: 1+5×4= 21 változónk és 5 + 5 + 52 = 20 egyenletünk maradt. Önkényesen hozzáadunk egy plusz feltételt: rögzítsük az elso˝ két egyenes (henger) szögét, legyenek egymásra ˝ merolegesek. – p. 17/43
A kapott többváltozós polinomrendszer
Az ℓ1 és ℓj (3 ≤ j ≤ 7) egyenesek távolsága: yj2 t2j + 2yj2 tj uj − 2yj2 tj + yj2 u2j − 2yj2 uj + yj2 + 2yj tj uj + 2yj u2j −
−2yj uj − 4t2j − 8tj uj + 8tj − 7u2j + 8uj − 4 = 0,
j = 3, . . . , 7.
Az ℓ2 és ℓj (3 ≤ j ≤ 7) egyenesek távolsága: x2j t2j + 2x2j tj uj − 2x2j tj + x2j u2j − 2x2j uj + x2j − 2xj tj uj − 2xj t2j +
+2xj tj − 4u2j − 8tj uj + 8tj − 7t2j + 8uj − 4 = 0,
j = 3, . . . , 7.
– p. 18/43
A kapott többváltozós polinomrendszer Az ℓi és ℓj (3 ≤ i < j ≤ 7) egyenesek távolsága:
−4xi yi ti ui tj uj +4xi xj ti ui tj uj +4xi yj ti ui tj uj +4yi xj ti ui tj uj +4yi yj ti ui tj uj −4xj yj ti ui tj uj −2x2i ti ui tj uj −2yi2 ti ui tj uj −2x2j ti ui tj uj −2yj2 ti ui tj uj −4xi xj ti ui uj +4xi xj ti u2j +4xi xj u2i tj −4xi xj ui tj uj +4yi yj t2i uj −4yi yj ti ui tj −4yi yj ti tj uj +4yi yj ui t2j +4xi xj ui uj +4yi yj ti tj +x2i t2i u2j +x2i u2i t2j +yi2 t2i u2j +yi2 u2i t2j +x2j t2i u2j +x2j u2i t2j +yj2 t2i u2j +yj2 u2i t2j +2xi yi t2i u2j +2xi yi u2i t2j −2xi xj t2i u2j −2xi xj u2i t2j −2xi yj t2i u2j −2xi yj u2i t2j −2yi xj t2i u2j −2yi xj u2i t2j −2yi yj t2i u2j −2yi yj u2i t2j +2xj yj t2i u2j +2xj yj u2i t2j −2xi yi t2i uj −2xi yi ti u2j +2xi yj t2i uj +2xi yj ti u2j +2xi yj u2i tj +2xi yj ui t2j −2xi yi u2i tj −2xi yi ui t2j +2yi xj t2i uj +2yi xj ti u2j +2yi xj u2i tj +2yi xj ui t2j −2xj yj t2i uj −2xj yj ti u2j −2xj yj u2i tj −2xj yj ui t2j −2x2i ti u2j −2x2i u2i tj −2yi2 t2i uj −2yi2 ui t2j −2x2j ti u2j −2x2j u2i tj −2yj2 t2i uj −2yj2 ui t2j +2x2i ti ui uj +2x2i ui tj uj +2yi2 ti ui tj +2yi2 ti tj uj +2x2j ti ui uj +2x2j ui tj uj +2yj2 ti ui tj +2yj2 ti tj uj +2xi yi ti ui tj +2xi yi ti ui uj +2xi yi ti tj uj +2xi yi ui tj uj −2xi yj ti ui tj −2xi yj ti ui uj −2xi yj ti tj uj −2xi yj ui tj uj −2yi xj ti ui tj −2yi xj ti ui uj −2yi xj ti tj uj −2yi xj ui tj uj +2xj yj ti ui tj +2xj yj ti ui uj +2xj yj ti tj uj +2xj yj ui tj uj −2x2i ui uj −2yi2 ti tj −2x2j ui uj −2yj2 ti tj −2xi yi ti ui +2xi yi ti uj +2xi yi ui tj −2xi yi tj uj +2xi yj ti ui −2xi yj ti uj −2xi yj ui tj +2xi yj tj uj +2yi xj ti ui −2yi xj ti uj −2yi xj ui tj +2yi xj tj uj −2xj yj ti ui +2xj yj ti uj +2xj yj ui tj −2xj yj tj uj −2xi xj u2i −2xi xj u2j −2yi yj t2j −2yi yj t2i +24ti ui tj uj +x2i u2i +x2i u2j +yi2 t2i +yi2 t2j +x2j u2i +x2j u2j +yj2 t2i +yj2 t2j −12t2i u2j −12u2i t2j −4t2i −4u2i −4t2j −4u2j −8ti ui tj −8ti ui uj −8ti tj uj +8ti u2j +8t2i uj +8u2i tj +8ui t2j −8ui tj uj +8ti tj +8ui uj = 0, i = 3, . . . , 6, j = i + 1, . . . , 7. – p. 19/43
Többváltozós polinomrendszerek megoldása
Néhány, a többváltozós polinomrendszerek megoldására ismert módszercsalád: Gröbner-bázisok Rezultáns módszer Általánosított rezultáns módszer Homotópiás módszer Newton-iteráció (lokális)
– p. 20/43
A homotópiás módszer
Drexler (1977) Garcia és Zangwill (1979) Morgan és Sommese (1987) Huber és Sturmfels (1995) Li (1997) Lee, Li és Tsai (2008) Chen, Lee és Li (2013)
– p. 21/43
A homotópiás módszer H(x, t) = (1 − t)Q(x) + tP (x) = 0
– p. 22/43
Két valós megoldás
A polinomrendszerünknek 121 milliárd megoldásjelöltje van, ezeket egyenként meg kell vizsgálni és kiválogatni a ˝ közremuködésével valósakat. Tsung-Lin Lee társszerzonk ˝ egy 12 magos Intel Xeon X5650 2.66 GHz gépen havonta 20 millió gyökjelölt vizsgálata történt meg. Az összes gyökjelölt vizsgálata így 6050 hónapig (504 évig) tartana. Szerencsére már 3 hónap után meglett az elso˝ valós gyök, majd még egy hónap múlva a második.
– p. 23/43
x3
11.675771704477
2.075088491891
y3
−4.124414157636
−2.036516392124
t3
0.704116159640
−0.030209763440
u3
0.235129952793
0.599691085438
x4
3.802878122730
−2.688893665930
y4
−2.910611127075
4.070505903499
t4
0.895623427074
0.184499043058
u4
−0.149726023342
0.426965115851
x5
8.311818491659
−4.033142850644
y5
−1.732276613733
−2.655943449984
t5
2.515897624878
0.251380280590
u5
−0.566129665502
0.516678258430
x6
−6.487945444917
6.311134419772
y6
−8.537495065091
−5.229892181735
t6
0.785632006191
−0.474742889365
u6
0.338461562103
1.230302197822
x7
−3.168475045360
3.914613907006
y7
−2.459640638529
−7.881492743224
t7
0.192767499267
1.698198197367
u7
0.536724141124
−1.164062857743
– p. 24/43
A gyökök tesztelése Meg kell vizsgálni, hogy nemcsak egy jó közelíto˝ megoldást kaptunk, hanem a polinomrendszernek valóban létezik izolált valós gyöke a kapott érték kis sugarú környezetében. Két gyöktesztelo˝ algoritmust alkalmaztunk:
alphaCertified, Smale α-elméletére építve
– p. 25/43
A gyökök tesztelése Meg kell vizsgálni, hogy nemcsak egy jó közelíto˝ megoldást kaptunk, hanem a polinomrendszernek valóban létezik izolált valós gyöke a kapott érték kis sugarú környezetében. Két gyöktesztelo˝ algoritmust alkalmaztunk:
alphaCertified, Smale α-elméletére építve Krawczyk intervallumos módszere
– p. 26/43
A gyökök tesztelése
˝ Mindkét eljárás megerosítette, hogy mindkét gyök „valódi”. Beláttuk tehát: ˝ végtelen hosszú, azonos Tétel: A páronként érintkezo, sugarú hengerek maximális száma legalább 7.
– p. 27/43
Az elso˝ megoldás
– p. 28/43
A második megoldás
– p. 29/43
– p. 30/43
˝ azonos (véges) Nyitott kérdések: páronként érintkezo, hosszú hengerek
Lehet-e találni 5-nél több érmét? Lehet-e találni 7-nél több cigarettát? Mit lehet mondani a köztes hossz/átméro˝ arányok esetében?
– p. 31/43
˝ végtelen hosszú Nyitott kérdések: páronként érintkezo, hengerek
Mi történik, ha változni engedjük az elso˝ két henger szögét, ami eddig derékszöget zárt be? A korábban kizárt irányvektorok (ti + ui + vi = 0) megengedése – és a ti + ui + vi 6= 0 irányvektorok kizárása – ad-e új megoldásokat? Lehet-e találni nyolcat? A bemutatott módszerrel felírt egyenletrendszerben 25 változó és 27 egyenlet szerepel. Meglepo˝ lenne, ha megoldható lenne, de a megoldhatatlanság bizonyítása sem tunik ˝ egyszerunek. ˝
– p. 32/43
˝ végtelen hosszú Nyitott kérdések: páronként érintkezo, hengerek
Mi történik, ha nem ragaszkodunk ahhoz, hogy a hengerek azonos sugarúak legyenek? Mi az Rn -beli (n > 3), páronként azonos (pozitív) távolságra lévo˝ egyenesek maximális száma?
– p. 33/43
˝ Fobb hivatkozások a páronként érintkezo˝ érmék témájában
Dudeney, H.E. (1917): Amusements in mathematics, Thomas Nelson and Sons, London, Edingburgh, New York, p. 143., p. 248. https://archive.org/details/amusementsinmath00dude https://openlibrary.org/books/OL178183M/Amusements_in_mathematics
Gardner, M. (1959): The Scientific American book of mathematical puzzles and diversions, Simon and Schuster, New York, pp. 110–115.
– p. 34/43
˝ Fobb hivatkozások a páronként érintkezo˝ cigaretták témájában
Gardner, M. (1959): The Scientific American Book of Mathematical Puzzles and Diversions, Simon and Schuster, New York, pp. 110–115. Grätzer, J. (1935): Rébusz, Singer és Wolfner Irodalmi Intézet, Budapest, 115. o., 233. o. ˝ L. (1997): Észjárások - A racionális gondolkodás Méro, korlátai és a mesterséges intelligencia, Tericum Kiadó, R8 rejtvény, 17–18. o., 183–184. o.
– p. 35/43
˝ ˝ végtelen Fobb hivatkozások a páronként érintkezo, hosszú hengerek témájában
Ambrus, G., Bezdek, A. (2008): On the number of mutually touching cylinders. Is it 8?, European Journal of Combinatorics 29(8):1803–1807. Bezdek, A. (2005): On the number of mutually touching cylinders, Combinatorial and Computational Geometry, MSRI Publication, 52:121–127. Brass, P., Moser, W., Pach, J. (2005): Research problems in discrete geometry, Springer. Littlewood, J.E. (1968): Some problems in real and complex analysis, Heath Mathematical Monographs, Raytheon Education, Lexington, Massachusetts. Ogilvy, C.S. (1962): Tomorrow’s math: unsolved problems for the amateur, Oxford Univesity Press, New York. – p. 36/43
˝ ˝ végtelen Fobb hivatkozások a páronként érintkezo, hosszú hengerek témájában
Pikhitsa, P.V. (2004): Regular network of contacting cylinders with implications for materials with negative Poisson ratios, Physical Review Letters 93(1) Article 015505. Pikhitsa, P.V. (2007): Architecture of cylinders with implications for materials with negative Poisson ratio, Physica Status Solidi B 244(3):1004–1007. Pikhitsa, P.V., Choi, M., Kim, H-J., Ahn, S-H. (2009): Auxetic lattice of multipods, Physica Status Solidi B 246(9):2098–2101. Pikhitsa, P.V., Choi, M. (2014): Seven, eight, and nine mutually touching infinitely long straight round cylinders: Entanglement in Euclidean space, manuscript, arXiv:1312.6207 – p. 37/43
˝ Fobb hivatkozások a homotópiás módszer témájában
Chen, T., Lee, T.L., Li, T.Y. (2014): Mixed volume computation in parallel, Taiwanese Journal of Mathematics, 18(1):93–114. Drexler, F.J. (1977): Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen, Numerische Mathematik 29(1):45–58. Garcia, C.B., Zangwill, W.I. (1979): Finding all solutions to polynomial systems and other systems of equations, Mathematical Programming 16(1):159–176. Huber, B., Sturmfels, B. (1995): A polyhedral method for solving sparse polynomial systems, Mathematics of Computation 64(212):1541–1555.
– p. 38/43
˝ Fobb hivatkozások a homotópiás módszer témájában
Lee, T.L., Li, T.Y., Tsai, C.H. (2008): HOM4PS-2.0, A software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing 83(2-3):109–133. Li, T.Y. (1997): Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numerica 6:399–436.
– p. 39/43
˝ Fobb hivatkozások a gyöktesztek témájában
Blum, L., Cucker, F., Shub, M., Smale, S. (1997): Complexity and real computation, Springer-Verlag, New York. Hauenstein, J.D., Sottile, F. (2012): Algorithm 921: alphaCertified: certifying solutions to polynomial systems, ACM Transactions on Mathematical Software 38(4): Article 28. DOI 10.1145/2331130.2331136 Krawczyk, R. (1969): Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4(3):187–201.
– p. 40/43
˝ Fobb hivatkozások a gyöktesztek témájában
Rump, S.M. (1999): INTLAB – INTerval LABoratory, in: Csendes, T., editor, Developments in reliable computing, Kluwer Academic Publishers, Dordrecht, pp. 77–104. Rump, S.M.: INTLAB – INTerval LABoratory. http://www.ti3.tu-harburg.de/rump/intlab/ Smale, S. (1986): Newton’s method estimates from data at one point, in Ewing, R.E., Gross, K.I., Martin, C.F. (editors): The merging of disciplines: new directions in pure, applied, and computational mathematics, Springer, New York, pp. 185–196.
– p. 41/43
– p. 42/43
Köszönöm a figyelmet.
[email protected] http://www.sztaki.mta.hu/∼bozoki
– p. 43/43
