2017의 가을에 메타압 소니매사추세츠 공과 대학의 학부생이었던 은 한 학기 동안 하나의 논문을 공부하기 위해 출발한 대학원 읽기 그룹에 합류했습니다. 그러나 학기 말에 Sawhney는 증명의 복잡성에 당황하여 계속 진행하기로 결정했다고 회상합니다. 그는 “정말 놀라웠다. "완전히 밖에 있는 것 같았어요."

논문은 피터 키바쉬 옥스포드 대학의. 주제: 디자인이라고 하는 수학적 대상.

디자인에 대한 연구는 1850년으로 거슬러 올라갑니다. 당시 영국 북부에 있는 한 교구의 교구 목사였던 Thomas Kirkman은 수학에 관심이 많았습니다. 숙녀와 신사의 일기. 15명의 여학생이 일주일 동안 매일 XNUMX열로 등교한다고 가정해 봅시다. 그것들을 정리할 수 있습니까? XNUMX일 동안 두 명의 소녀가 같은 줄에 한 번 이상 있는 경우가 없습니까?

곧 수학자들은 Kirkman의 질문에 대한 보다 일반적인 버전을 묻기 시작했습니다. n 세트의 요소(15명의 여학생)를 크기별로 그룹화할 수 있습니까? k (행 XNUMX개) 작은 크기의 모든 세트가 t (모든 소녀 쌍)이 정확히 그 그룹 중 하나에 나타납니까?

이러한 구성은 (n, k, t) 디자인은 이후 오류 수정 코드, 디자인 실험, 테스트 소프트웨어 개발, 스포츠 대진표 및 복권 당첨을 돕는 데 사용되었습니다.

그러나 그들은 또한 다음과 같이 구성하기가 매우 어려워집니다. k 과 t 더 커집니다. 사실, 수학자들은 아직 값이 다음과 같은 디자인을 찾지 못했습니다. t 5보다 큽니다. 그래서 2014년에 Keevash가 보여 이러한 디자인을 만드는 방법을 모르더라도 그들은 항상 존재한다, 한 n 충분히 크고 몇 가지 간단한 조건을 충족합니다.

이제 Keevash, Sawhney 및 애쉬윈 사MIT의 대학원생인 은 부분 공간 설계라고 하는 훨씬 더 파악하기 어려운 객체가 항상 또한 존재한다. "그들은 그 존재가 전혀 명백하지 않은 물체의 존재를 증명했습니다."라고 말했습니다. 데이비드 콘론, 캘리포니아 공과 대학의 수학자.

그렇게 하기 위해 그들은 훨씬 더 제한적인 환경에서 작동하도록 무작위성과 신중한 구성의 거의 마술적인 혼합을 포함하는 Keevash의 원래 접근 방식을 수정해야 했습니다. 그래서 현재 MIT에서 박사 과정을 밟고 있는 Sawhney는 불과 몇 년 전에 그를 당황하게 했던 논문과 대면하게 되었습니다. "기술을 완전히 이해하고 실제로 고통을 겪고 작업하고 개발하는 것이 정말 정말 즐거웠습니다."라고 그는 말했습니다.

'우리의 상상을 초월하는 그 너머'

수십 년 동안 수학자들은 설계 질문과 같은 집합 및 부분 집합에 대한 문제를 소위 벡터 공간 및 부분 공간에 대한 문제로 번역했습니다.

벡터 공간은 요소(벡터)가 단순한 점 집합보다 훨씬 더 엄격한 방식으로 서로 관련되어 있는 특별한 종류의 집합입니다. 포인트는 현재 위치를 알려줍니다. 벡터는 이동한 거리와 방향을 알려줍니다. 더하거나 뺄 수 있고 더 크게 또는 더 작게 만들 수 있습니다.

당신이 있는 방을 생각해 보십시오. 여기에는 무한한 수의 점과 무한한 수의 벡터가 포함되어 있습니다. 벡터는 당신이 있는 곳에서 방의 모든 점까지 뻗어 있습니다. 이러한 모든 벡터는 세 가지 기본 요소, 즉 앞을 가로로 가리키는 벡터, 오른쪽을 가리키는 벡터, 위쪽을 가리키는 벡터로 구성할 수 있습니다. 이러한 벡터를 더하거나 실수로 곱하거나 두 가지를 조합하여 사용자가 살고 있는 XNUMX차원 벡터 공간을 생성할 수 있습니다. (전체 공간을 생성하는 데 필요한 벡터의 수는 벡터 공간의 차원입니다.)

다양한 부분 공간이 각 벡터 공간 안에 있습니다. 오른쪽과 앞을 가리키는 벡터만 가져옵니다. 이것들은 바닥과 평행한 평면인 XNUMX차원 부분 공간을 정의합니다.

수학자들은 종종 벡터가 가능한 모든 방향을 가리킬 수 없고 동일한 길이 개념을 갖지 않는 유한 벡터 공간 및 부분 공간으로 작업합니다. 이 세계에서 각 벡터 공간에는 유한한 수의 벡터만 있습니다.

부분공간 설계 문제는 다음을 다룹니다. n-차원 벡터 공간 및 해당 부분 공간. 그러한 벡터 공간에서 — 다시 한 번 n 충분히 크고 간단한 조건을 만족합니다. k-차원 부분공간 t- 차원 부분 공간은 정확히 그들 중 하나에 포함되어 있습니까? 이러한 객체를 (n, k, t) 부분공간 설계. 일반적인 디자인 문제와 개념적으로 유사하지만 훨씬 더 엄격하게 제한되는 배열을 포함합니다.

"그것은 한편으로는 집합과 부분 집합, 다른 한편으로는 벡터 공간과 부분 공간 사이의 매우 깊은 유추의 한 구석이기 때문에 중요한 문제입니다."라고 말했습니다. 피터 카메론 스코틀랜드의 세인트앤드루스 대학교.

수학자들이 이 문제에 대해 생각하기 시작한 이래로 50년 동안 그들은 다음을 발견했습니다. 단 하나의 사소한 예 (더 일반적인 종류의 부분 공간 디자인이 존재한다는 것을 알고 있지만): 13차원 벡터 공간에서 XNUMX차원 부분 공간을 XNUMX차원 부분 공간으로 정확히 한 번 덮는 것이 가능합니다. 결과는 엄청난 컴퓨터 기반 증명이 필요했습니다. n, k 과 t, 결국 수백만 개의 부분 공간으로 작업하게 됩니다. 그러한 시스템의 복잡성은 “우리의 상상을 초월하는 것이 아닙니다. 그것은 우리의 상상을 초월하는 것입니다.”라고 말했습니다. 투비 에치온 예를 발견하는 데 도움을 준 이스라엘의 Technion의.

그러나 부분공간 설계는 항상 존재합니까? k 과 t? 일부 수학자들은 대체로 그러한 물체는 불가능하다고 추측했습니다. 다른 사람들은 디자인에 대한 수년에 걸친 작업에 고무되어 "증명하기 어려울 수 있지만 존재하지 않을 분명한 이유가 없다면 존재해야 합니다"라고 Keevash는 말했습니다.

디자인 영역과 비교할 때 "이 문제에 대해서는 아무 것도 없었습니다."라고 Sah는 말했습니다. "그럴 때마다 약간의 호기심을 불러일으키는 것 같아요."

오류에 대한 스펀지

사와 소니 2017년 학부생으로 만난 MIT에서 (그리고 결국 같은 독서 그룹에 참석하게 되었습니다). 몇 달 후 "그들은 함께 일하기 시작했고 결코 멈추지 않았습니다."라고 Conlon은 말했습니다. “눈도 깜빡할 수 없을 정도로 수준 높은 연구를 하고 있습니다.”

두 젊은 수학자들은 부분 공간 디자인의 명시적인 예를 하나만 적는 것이 너무 어려웠고, 그 문제를 조합론에서 중요한 기술의 경계를 탐구하는 완벽한 방법으로 보았습니다.

한편 Keevash는 2014년 결과 이후로 이 질문을 마음 속에 간직해 왔습니다. Sah와 Sawhney가 작년 회의에서 그에게 접근했을 때 세 사람은 그것을 하기로 결정했습니다.

그들은 Keevash가 그의 디자인 작업에서 제시한 것과 동일한 전체 전략을 따랐지만 당면한 제약이 더 엄격했기 때문에 "실제로 모든 단계는 구현에서 매우 다르게 끝났습니다."라고 Keevash는 말했습니다. 먼저 템플릿이라고 하는 신중하게 선택된 하위 공간 집합을 따로 둡니다. 템플릿은 나중에 임의성의 바다에서 구조의 섬 역할을 합니다.

그런 다음 Rödl 니블(Rödl nibble)이라고 하는 근본적으로 무작위 프로세스의 수정된 버전을 적용하여 나머지 부분 공간의 대부분을 처리했습니다. 그것은 그들이 여전히 처리해야 하는 부분 공간의 희박한 잡동사니를 남겼습니다. 표면적으로 이러한 부분 공간은 완전히 구조화되지 않은 것처럼 보였습니다. 적절하게 덮을 수 있는 클러스터로 그것들을 배열하는 것은 불가능해 보였습니다.

그것이 템플릿이 등장한 곳입니다. 그들은 템플릿을 조각으로 나누고 하위 공간의 일부를 잡동사니의 하위 공간과 결합했습니다. 그들은 그들이 하는 모든 움직임이 더 큰 글로벌 구조로 이어지도록 하기 위해 그들이 어떻게 하고 있는지 주의 깊게 추적해야 했습니다. 그러나 궁극적으로 그들은 템플릿을 사용하여 Rödl 니블이 덮을 수 없었던 모든 구멍을 채울 수 있었습니다. 스펀지처럼 템플릿은 디자인 내의 모든 오류를 흡수했습니다. (결과적으로 이 일반적인 기술을 "흡수"라고 합니다.) Sawhney는 "모퉁이에 카펫을 깔려고 하는 것과 거의 같습니다."라고 말했습니다. "그것은 다른 곳에서 튀어나오고, 당신이 그것을 밀고, 어떻게든 20번 밀고 나면, 카펫은 그냥 평평해집니다."

이로써 증명이 완료되었습니다. 디자인 작업과 마찬가지로 이 결과는 적어도 이론적으로는 이러한 객체를 구성하는 데 사용될 수 있지만 매우 큰 n. 구체적이고 실용적인 예를 찾는 것은 미래의 과제로 남아 있습니다.

결국 작품은 삽화 또 다른 반직관적인 방법 수학자들은 숨겨진 구조를 찾기 위해 무작위성의 힘을 이용할 수 있습니다. "모든 종류의 예상치 못한 구조가 가능하다"고 말했다. 셰릴 프레거, 웨스턴 오스트레일리아 대학의 수학자.

"증거는 Keevash의 기술이 설계된 것보다 더 넓은 맥락에서 작동한다는 것을 보여줍니다."라고 Cameron이 말했습니다. 이는 임의성과 흡수를 영리한 방식으로 결합하여 다른 어려운 문제를 해결할 수 있음을 의미합니다.

이러한 기술은 Sawhney가 학부 시절 Keevash의 논문에서 처음 읽었을 때 마술처럼 느껴졌습니다. 그들에 대해 훨씬 더 깊이 이해하게 된 지금도 "이 감동은 사라지지 않는다."