Kontaktnummer

Kontaktnummer (ibland Newtons nummer [1] [2] , i kemi motsvarar koordinationsnumret [2] ) - det maximala antalet bollar med enhetsradie som samtidigt kan vidröra en av samma boll i n - dimensionellt euklidiskt rymd (det antas att bollarna inte tränger in i varandra, det vill säga att skärningsvolymen mellan två kulor är lika med noll).

Det är nödvändigt att skilja kontaktnumret från kontaktnumret på gittret [3]  - en liknande parameter för den tätaste regelbundna packningen av bollar . Beräkningen av kontaktnumret i det allmänna fallet är fortfarande ett olöst matematiskt problem .

Historik

I det endimensionella fallet kan inte mer än två segment av enhetslängd röra samma segment:

I det tvådimensionella fallet kan problemet tolkas som att hitta det maximala antalet mynt som rör det centrala. Bilden visar att du kan placera upp till 6 mynt:

Detta betyder att . Å andra sidan skär varje tangentcirkel av en båge på 60° på den centrala cirkeln, och dessa bågar skär sig inte, så . Det kan ses att i det här fallet sammanfaller uppskattningarna från ovan och nedan och .

I det tredimensionella fallet talar vi om bollar. Här är det också lätt att konstruera ett exempel med 12 bollar som rör vid den centrala - de är placerade vid ikonernas hörn -  därför . Denna nedre gräns var redan känd för Newton .

Detta arrangemang är löst, det kommer att finnas ganska märkbara luckor mellan bollarna. Uppskattningen från ovan blev orsaken till den välkända tvisten mellan Newton och D. Gregory 1694. Newton hävdade att , och Gregory invände att det kunde vara möjligt att arrangera 13 bollar. Han utförde beräkningar och fann att arean av den centrala bollen är mer än 14 gånger arean för projektionen av var och en av de rörande bollarna, så . Om du tillåter att ändra kulornas radier med 2%, är det möjligt att luta upp till 14 bollar.

Först 1953, i en artikel av Schütte och van der Waerden [4] , slogs det slutligen fast att Newton hade rätt, trots bristen på ett rigoröst bevis.

I det fyrdimensionella fallet är det ganska svårt att föreställa sig bollar. Placeringen av 24 fyrdimensionella sfärer runt den centrala har varit känd under lång tid , den är lika regelbunden som i det tvådimensionella fallet och löser samtidigt kontaktnummerproblemet på gallret. Detta är samma placering som heltalsenhetskvaternioner .

Detta arrangemang angavs uttryckligen 1900 av Gosset [5] . Ännu tidigare hittades den (i ett motsvarande problem) 1872 av de ryska matematikerna Korkin och Zolotarev [6] [7] . Denna plats gav ett betyg underifrån .

Försök att uppskatta detta antal från ovan ledde till utvecklingen av subtila metoder för funktionsteori, men gav inget exakt resultat. Först lyckades vi bevisa det , sedan lyckades vi minska den övre gränsen till . Slutligen, 2003, lyckades den ryske matematikern Oleg Musin bevisa att [8] .

I dimensionerna 8 och 24 erhölls en exakt uppskattning på 1970 -talet [9] [10] . Beviset är baserat på likheten mellan kontaktnumret och kontaktnumret på gallret i dessa dimensioner: E8-gallret (för dimension 8) och Leach-gallret (för dimension 24).

Kända värden och uppskattningar

För närvarande är de exakta värdena på kontaktnumren kända endast för , men också för och . För vissa andra värden är övre och nedre gränser kända.

Dimensionera Slutsats Övre gräns
ett 2
2 6
3 12
fyra 24 [8]
5 40 44 [11]
6 72 78 [11]
7 126 134 [11]
åtta 240
9 306 364 [11]
tio 500 554
elva 582 870
12 840 1 357
13 1154 [12] 2069
fjorton 1606 [12] 3 183
femton 2564 4 866
16 4 320 7 355
17 5 346 11 072
arton 7 398 16 572 [11]
19 10 688 24 812 [11]
tjugo 17 400 36 764 [11]
21 27 720 54 584 [11]
22 49 896 82 340
23 93 150 124 416
24 196 560

Applikationer

Problemet har praktisk tillämpning i kodningsteori. 1948 publicerade Claude Shannon ett informationsteoridokument som visar möjligheten till felfri dataöverföring i bullriga kommunikationskanaler med hjälp av packningskoordinaterna för enhetssfärer i n-dimensionellt rymd. Se även Hamming distans .

Se även

Anteckningar

  1. Yaglom, I. M. Trettonbollsproblemet . - Kiev: Vishcha-skolan, 1975. - 84 sid.
  2. 1 2 J. Conway, N. Sloan. Packningar av kulor, galler och grupper . - M . : Mir, 1990. - T. 1. - 415 sid. — ISBN 5-03-002368-2 . Arkiverad kopia (inte tillgänglig länk) . Hämtad 29 maj 2011. Arkiverad från originalet 6 oktober 2014. 
  3. Nätkontaktnummer : OEIS - sekvens A001116
  4. Schütte, K. och van der Waerden, BL Das Problem der dreizehn Kugeln  (obestämd)  // Math. Ann. . - 1953. - T. 125 , nr 1 . - S. 325-334 . - doi : 10.1007/BF01343127 .
  5. Gosset, Thorold. På de reguljära och halvreguljära figurerna i rymden av n dimensioner  //  Messenger of Mathematics : journal. - 1900. - Vol. 29 . - S. 43-48 .
  6. Korkine A., Zolotareff G. Sur les formesatiques positives quaternaires  (neopr.)  // Math. Ann. . - 1872. - V. 5 , nr 4 . - S. 581-583 . - doi : 10.1007/BF01442912 . Rus. översättning: Zolotarev E. I. Fullständig. coll. op. - L . : Publishing House of the Academy of Sciences of the USSR, 1931. - S. 66-68.
  7. N. N. Andreev, V. A. Yudin. Arfimetiskt minimum av kvadratisk form och sfäriska koder  // Matematisk utbildning . - 1998. - Nr 2 . - S. 133-140 .
  8. 1 2 Musin O. R. Problemet med tjugofem sfärer  // Framsteg inom matematiska vetenskaper . - Ryska vetenskapsakademin , 2003. - T. 58 , nr 4 (352) . - S. 153-154 .
  9. Levenshtein V. I. Om gränser för packningar i n -dimensionell euklidisk rymd // DAN SSSR. - 1979. - T. 245 . - S. 1299-1303 .
  10. A.M. Odlyzko, NJA Sloane. Nya gränser för antalet enhetssfärer som kan röra en enhetssfär i n dimensioner  //  J. Combin. Teori Ser. A  : dagbok. - 1979. - Vol. 26 . - S. 210-214 . - doi : 10.1016/0097-3165(79)90074-8 .
  11. 1 2 3 4 5 6 7 8 Hans D. Mittelmann och Frank Vallentin. [ http://arxiv.org/abs/0902.1105 Semidefinita programmeringsgränser med hög precision för kyssande tal] // Experimentell matematik. - 2010. - T. 19 , nr 2 . - S. 174-178 .
  12. 1 2 V. A. Zinoviev, T. Erickson. Nya nedre gränser för kontaktnumret för små dimensioner  // Probl. överföring av information .. - 1999. - T. 35 , nr 4 . - S. 3-11 .

Länkar