키스번호

Kissing number

기하학에서, 수학 공간의 키스 번호는 각각 공통 단위 구를 만질 수 있도록 그 공간에 배열될 수 있는 가장 많은 수의 겹치지 않는 단위 구로 정의된다. 주어진 공간에 주어진 구(구) 패킹(구)의 경우, 각각의 구(구)가 닿는 구(區)의 수로 키스 번호를 정의할 수도 있다. 격자 패킹의 경우 모든 구에 대해 키스 번호가 동일하지만 임의 구를 패킹하는 경우 키스 번호는 구마다 다를 수 있다.

지금까지 사용된 키스 번호의 다른 이름으로는 뉴턴 번호(문제의 원점 이후)와 연락처 등이 있다.

일반적으로 키스 번호 문제는 (n + 1)차원 유클리드 공간에서 n차원 에 대해 가능한 최대 키스 수를 찾는다. 보통의 구들은 3차원 공간에서 2차원 폐쇄면에 해당한다.

구의 중심이 선(일차원 케이스)이나 평면(이차원 케이스)에 국한되어 있을 때 키스 번호를 찾는 것은 사소한 일이다. 물리적 세계에서 개념화 및 모델링이 용이함에도 불구하고, 20세기 중반까지 수학자들을 피한 3차원 사례에 대한 해결책의 입증.[1][2] 더 높은 차원의 해결은 상당히 더 어려우며, 정확히 해결된 사례는 극히 일부에 불과하다. 다른 조사에서는 상한과 하한을 결정했지만 정확한 해결책은 아니다.[3]

알려진 가장 큰 키스 숫자

원차원

한 차원에서는 키스 번호가 2:[4]

Kissing-1d.svg

2차원

2차원에서 키스 번호는 6:

Kissing-2d.svg

증명: C 중심C1 중심2 C, ... 중심과 원과 접촉하는 C 중심 원을 생각해 보십시오. 광선 Ci 고려하라. 이 광선들은 모두 같은 중심 C에서 발산되기 때문에 인접한 광선 사이의 각도의 합은 360°이다.

6개 이상의 터치 서클이 있다고 모순으로 가정한다. 그런 다음 최소 두 개의 인접 광선(: C C1 C C2)이 60° 미만의 각도로 분리된다. 세그먼트 Ci 모든 i에 대해 길이가 같다 – 2r –. 따라서 삼각형 C C C12 등각형이며, 세 번째 면인 C C12 옆면 길이가 2r 미만이다. 그러므로 원 1과 2는 교차한다 – 모순이다.[5]

키스 번호 12를 3차원으로 대칭적으로 실현하는 것은 외부 구들의 중심을 일반 이코사헤드론의 정점에 맞추어 정렬하는 것이다. 이것은 근처의 두 구 사이의 반경의 0.1을 약간 넘는 것을 남긴다.

삼차원

3차원에서는 키스 번호가 12이지만 정확한 값은 1, 2차원보다 훨씬 설정하기가 어려웠다. 12개의 구를 배열하여 각각 중심 구를 건드리기는 쉽지만, 남은 공간이 많고, 13구 안에 짐을 꾸릴 방법이 없는 것은 분명하지 않다.(사실 12개의 외구 중 2개라도 원뿔을 잃지 않고 연속적인 운동을 통해 장소를 교환할 수 있을 정도로 여분의 공간이 많다.1번 가운데로 재치있게) 이것은 수학자 아이작 뉴턴데이비드 그레고리의 유명한 의견 불일치의 주제였다. 뉴턴은 그 한계가 12라고 정확히 생각했다; 그레고리는 13번째가 맞을 수 있다고 생각했다. 뉴턴이 옳았다는 일부 불완전한 증거는 19세기에 제시되었는데, 가장 두드러지게는 라인홀드 호페에 의해 제시되었지만, 최초의 정확한 증거(브라스, 모저, 파흐에 따르면)는 1953년까지 나타나지 않았다.[1][2][6]

중심 영역의 12개의 이웃은 모든 원자가 같은 크기(화학 원소처럼)를 갖는 결정 격자 안에 있는 원자의 최대 대량 조정 번호에 해당한다. 밀폐형 또는 육각형 밀폐형 구조에서 12의 조정 번호를 찾을 수 있다.

큰 치수

4차원으로 보면 얼마 전부터 답이 24나 25인 것으로 알려져 있었다. 중심 구를 중심으로 24개의 구를 포장을 제작하는 것이 간단하다(원점을 중심으로 적절히 크기가 조정된 24셀의 정점에 구를 배치할 수 있다). 3차원 사례에서와 같이, n = 3보다 훨씬 더 많은 공간이 남아 있기 때문에 상황은 더욱 분명하지 않았다. 2003년에 올레그 무신은 n = 4가 24가 되는 키스 수를 증명했다.[7][8]

n 치수의 키스 번호는 n = 8(240), n = 24(196,560)를 제외하고 n > 4에 대해 알 수 없다.[9][10] 이러한 차원의 결과는 매우 대칭적인 격자(E8 격자Leech 격자)의 존재에서 비롯된다.

구들의 중심이 모두 격자의 점에 놓여 있는 격자 배열로 배치가 제한되는 경우, 이 제한된 키스 번호는 n = 1 - 9 및 n = 24 치수로 알려져 있다.[11] 5, 6, 7차원의 경우 지금까지 발견된 가장 높은 알려진 키스 번호를 가진 배열이 최적의 격자 배열이지만, 더 높은 키스 번호를 가진 비 격자 배열의 존재는 제외되지 않았다.

일부 알려진 한계

다음 표에는 다양한 차원의 키스 번호에 대해 알려진 몇 가지 한계가 나와 있다.[12] 키스 번호가 알려진 치수는 굵은 글씨로 나열되어 있다.

대략적인 볼륨 추정치는 n차원의 키스 수가 n차원기하급수적으로 증가한다는 것을 보여준다. 기하급수적인 성장의 근거는 알려져 있지 않다. 위의 그림에서 회색 영역은 알려진 상한과 하한 사이의 가능한 값을 나타낸다. 원은 정확히 알려진 가치를 나타낸다.
치수 더 낮게
묶인
상부
묶인
1 2
2 6
3 12
4 24[7]
5 40 44
6 72 78
7 126 134
8 240
9 306 363
10 500 553
11 582 869
12 840 1,356
13 1,154[13] 2,066
14 1,606[13] 3,177
15 2,564 4,858
16 4,320 7,332
17 5,346 11,014
18 7,398 16,469
19 10,668 24,575
20 17,400 36,402
21 27,720 53,878
22 49,896 81,376
23 93,150 123,328
24 196,560

일반화

키스 번호 문제는 신체 특정 사본을 만지는 볼록한 신체의 최대 비 겹치지 않는 결합 복제본을 찾는 문제로 일반화될 수 있다. 사본은 본문에만 합치도록 되어 있는지, 본문을 번역해야 하는지, 격자로 번역해야 하는지에 따라 문제의 버전이 다르다. 예를 들어 일반 사면체의 경우 격자키스 번호와 번역 키스 번호는 모두 18과 동일한 반면 합체 키스 번호는 최소 56인 것으로 알려져 있다.[14]

알고리즘

교차로 그래프에는 키스 수에 따라 근사비가 달라지는 몇 가지 근사 알고리즘이 있다.[15] 예를 들어, 회전 장치 사각형 집합의 최대 비절연 부분집합을 찾기 위한 다항 시간 10 근사치 알고리즘이 있다.

수식문

키스 번호 문제는 일련의 불평등에 대한 해결책의 존재라고 말할 수 있다. 를 구 중심의 N D차원 위치 벡터 집합으로 한다. 이 구 집합이 중첩되지 않고 중심구 주위에 놓여질 수 있는 조건은 다음과 같다.[16]

따라서 각 차원에 대한 문제는 실존적 실존적 이론으로 표현될 수 있다. 그러나 이 형식의 일반적인 문제 해결 방법은 최소한 기하급수적인 시간이 소요되기 때문에 이 문제는 4차원까지만 해결되었다. 변수를 추가하여 y n } NN - 1)/2 + DN 변수의 단일 사분위 방정식으로 변환할 수 있다.[17]

따라서 D = 5차원 및 N = 40 + 1 벡터의 사례를 해결하려면 1025 변수의 사분위 다항식(squitic polyomial)에 대한 실제 해결책의 존재를 결정하는 것과 같을 것이다. D = 24 치수와 N = 196560 + 1의 경우, 사분위는 19,322,732,544개의 변수를 가질 것이다. 거리 기하학 측면에서 대체 문장은 mth nth 구체 사이의 제곱 거리로 제시된다.

이는 Cayley-Menger 결정요소D 치수의 심플렉스(D + 1)를 형성하는 모든 점 집합에 대해 0이라는 조건으로 보충되어야 한다. 그 부피는 0이어야 하기 때문이다. = 1+ y 실제 값에 대해서만 해결해야 하는 동시 다항식 세트를 y에 제공한다. 전적으로 동등한 두 가지 방법은 다양한 용도를 가지고 있다. 예를 들어, 두 번째 경우에는 y의 값을 작은 양으로 임의로 변경하여 y의 측면에서 다항식을 최소화하도록 할 수 있다.

참고 항목

메모들

  1. ^ a b Conway, John H.; Neil J.A. Sloane (1999). Sphere Packings, Lattices and Groups (3rd ed.). New York: Springer-Verlag. p. 21. ISBN 0-387-98585-9.
  2. ^ a b Brass, Peter; Moser, W. O. J.; Pach, János (2005). Research problems in discrete geometry. Springer. p. 93. ISBN 978-0-387-23815-9.
  3. ^ Mittelmann, Hans D.; Vallentin, Frank (2010). "High accuracy semidefinite programming bounds for kissing numbers". Experimental Mathematics. 19 (2): 174–178. arXiv:0902.1105. Bibcode:2009arXiv0902.1105M. doi:10.1080/10586458.2010.10129070. S2CID 218279.
  4. ^ 한 차원에서는 "스페어"가 단위 거리로 분리된 점의 쌍에 불과하다는 점에 유의하십시오. (1차원 그림의 수직 치수는 단지 환기할 뿐이다.) 고차원과는 달리 구내부(단위 길이 개방 간격)가 서로 겹치지 않도록 명시할 필요가 있다.
  5. ^ Lemma 3.1인치 참조
  6. ^ 종 호, Chuanming(2008년),"볼록 몸의, 번호를 차단하고 덮고 있는 번호 키스를 하고 번호", 굿맨, 야곱은 E에서의;.이산과 해석 기하학에 Pach, J├ínos, 폴락, 리차드(eds.), 조사:.20몇년 후에(AMS-IMS-SIAM 합동 하계 연구 회의, 6월 18ÔÇô22, 2006년 Snowbird, 유타), 현대 수학, 453년, 프로비던스, R1:미국 수학회,를 대신하여 서명함. 529–548, doi:10.1090/conm/453/08812, 아이 에스비엔 9780821842393, MR2405694.
  7. ^ a b O. R. Musin (2003). "The problem of the twenty-five spheres". Russ. Math. Surv. 58 (4): 794–795. Bibcode:2003RuMaS..58..794M. doi:10.1070/RM2003v058n04ABEH000651.
  8. ^ Pfender, Florian; Ziegler, Günter M. (September 2004). "Kissing numbers, sphere packings, and some unexpected proofs" (PDF). Notices of the American Mathematical Society: 873–883..
  9. ^ Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [On bounds for packings in n-dimensional Euclidean space]. Doklady Akademii Nauk SSSR (in Russian). 245 (6): 1299–1303.
  10. ^ 오드리즈코, A.M. 슬로운, N.J.A. 단위 구를 n차원으로 만질 수 있는 단위 구 수에 대한 새로운 한계. J. 콤빈. 이론 서. A 26 (1979년), 2,010번 - 210번
  11. ^ Weisstein, Eric W. "Kissing Number". MathWorld.
  12. ^ Machado, Fabrício C.; Oliveira, Fernando M. (2018). "Improving the Semidefinite Programming Bound for the Kissing Number by Exploiting Polynomial Symmetry". Experimental Mathematics. 27 (3): 362–369. arXiv:1609.05167. doi:10.1080/10586458.2017.1286273. S2CID 52903026.
  13. ^ a b В. А. Зиновьев, Т. Эриксон (1999). Новые нижние оценки на контактное число для небольших размерностей. Пробл. Передачи Информ. (in Russian). 35 (4): 3–11. 영어 번역:
  14. ^ Lagarias, Jeffrey C.; Zong, Chuanming (December 2012). "Mysteries in packing regular tetrahedra" (PDF). Notices of the American Mathematical Society: 1540–1549.
  15. ^ Kammer, Frank; Tholey, Torsten (July 2012). "Approximation Algorithms for Intersection Graphs". Algorithmica. 68 (2): 312–336. doi:10.1007/s00453-012-9671-1. S2CID 3065780.
  16. ^ 숫자 mn은 1에서 N까지 실행된다. =( x ) N 위치 벡터의 시퀀스다. mn을 교환하면 두 번째 범용 정량자) 뒤의 조건이 바뀌지 않기 때문에, 이 정량자가 , : m< : < 단순화를 위해 구 반경은 1/2로 가정한다.
  17. ^ 행렬 =( m ) 에 대해서는 m < n을 가진 항목만 있으면 된다. 또는 동등하게, 행렬은 대칭성이라고 가정할 수 있다. 어쨌든 행렬에는 자유 스칼라 변수가 N(N - 1)/2개만 있다. 외에도 행렬 x = ( n) 에 특파원이 되는 N D차원 벡터 xn 있다.N열 벡터 D

참조

외부 링크