개요
XNUMX월 중순, 저스틴 길머 친구의 결혼식에 참석하기 위해 캘리포니아에서 뉴욕으로 날아갔습니다. 동부 해안에 있는 동안 그는 그의 전 고문을 방문했습니다. 마이클 삭스, Gilmer가 XNUMX년 전에 박사 학위를 받은 Rutgers 대학의 수학자.
Saks와 Gilmer는 점심을 함께 먹었지만 수학에 대해서는 이야기하지 않았습니다. 사실 Gilmer는 2015년에 Rutgers를 졸업한 이후로 수학에 대해 심각하게 생각하지 않았습니다. 그때부터 그는 학계에서 경력을 쌓고 싶지 않다고 결정하고 대신 프로그래밍을 독학하기 시작했습니다. 그와 Saks가 식사를 하면서 Gilmer는 옛 멘토에게 자신이 Google에서 머신 러닝과 인공 지능을 연구하는 직업에 대해 이야기했습니다.
Gilmer가 Rutgers를 방문한 날은 화창했습니다. 돌아다니면서 그는 2013년에 노조 폐쇄 추측이라는 문제에 대해 생각하면서 같은 캠퍼스 길을 걸으며 XNUMX년의 대부분을 어떻게 보냈는지 회상했습니다. 비록 결실은 없었지만 그것은 고착이었습니다. 그의 모든 노력에도 불구하고 Gilmer는 숫자 집합에 대한 단순해 보이는 문제가 해결하기 어려운 이유를 스스로 터득하는 데 성공했을 뿐입니다.
“많은 사람들이 문제가 어려운 이유를 이해하고 만족할 때까지 문제에 대해 생각한다고 생각합니다. 아마도 대부분의 사람들보다 더 많은 시간을 보냈을 것입니다.”라고 Gilmer는 말했습니다.
16월 방문 이후 예상치 못한 일이 발생했습니다. 그는 새로운 아이디어를 얻었습니다. Gilmer는 통합 폐쇄 추측을 풀기 위해 정보 이론의 기술을 적용하는 방법에 대해 생각하기 시작했습니다. 그는 매번 실패할 것을 예상하면서 한 달 동안 아이디어를 추구했습니다. 그러나 그 대신 증명의 길이 계속 열렸습니다. 드디어 XNUMX월 XNUMX일 최초의 결과를 게시했습니다. 그것은 수학자들이 완전한 추측을 증명하는 데 많은 도움이 됩니다.
이 논문은 후속 작업을 시작했습니다. 옥스퍼드 대학교, 매사추세츠 공과대학, 고등연구소 등의 수학자들은 길머의 새로운 방법을 빠르게 구축했습니다. 그러나 그들이 그렇게 하기 전에 그들은 그들 자신의 질문을 했습니다. 이 사람은 누구입니까?
반쯤 찬
Union-closed 추측은 {1, 2} 및 {2, 3, 4}와 같은 집합이라고 하는 숫자 모음에 관한 것입니다. 합집합을 포함하여 집합에 대한 작업을 수행할 수 있습니다. 예를 들어 {1, 2}와 {2, 3, 4}의 합집합은 {1, 2, 3, 4}입니다.
세트의 컬렉션 또는 패밀리는 패밀리에 있는 두 세트의 합집합이 패밀리의 기존 세트와 동일한 경우 "유니온 폐쇄"로 간주됩니다. 예를 들어 다음과 같은 XNUMX개의 세트로 구성된 제품군을 고려하십시오.
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
쌍을 결합하면 이미 가족에 속한 세트를 얻게 되어 가족이 폐쇄된 상태가 됩니다.
수학자들은 1960년대까지 노조 폐쇄 추측의 버전에 대해 대화를 나눴지만 1979년에 의 논문에서 처음으로 공식적인 진술을 받았습니다. 피터 프랭클1980년대에 일본으로 이주한 헝가리 수학자.
프랭클은 집합집합이 합집합폐쇄라면 적어도 집합의 절반에 나타나는 하나 이상의 요소(또는 숫자)를 가져야 한다고 추측했습니다. 두 가지 이유로 자연스러운 문턱이었습니다.
첫째, 집합의 정확히 50%에 모든 요소가 나타나는 합집합 폐쇄 패밀리의 예를 쉽게 사용할 수 있습니다. 예를 들어 1에서 10까지 숫자로 만들 수 있는 모든 다른 세트와 마찬가지로. 이러한 집합은 1,024개이며 폐쇄형 가족을 형성하고 10개의 요소가 각각 512개에 나타납니다. 둘째, 프랭클이 추측을 했을 당시에는 누구도 추측이 성립하지 않는 노조 폐쇄 가족의 예를 제시한 적이 없었습니다.
따라서 50%가 올바른 예측처럼 보였습니다.
증명하기가 쉽지 않았다는 뜻입니다. Frankl의 논문 이후 몇 년 동안 결과가 거의 없었습니다. Gilmer의 작업 이전에 이러한 논문은 패밀리의 세트 수에 따라 달라지는 임계값만 설정했습니다(모든 규모의 세트 패밀리에 대해 동일한 50% 임계값이 되는 것과는 반대로).
"쉬워야 할 것 같은 느낌이고, 쉬운 많은 문제와 비슷하지만 공격에 저항했습니다."라고 말했습니다. 윌 사윈 콜롬비아 대학의.
진보의 부족은 문제의 까다로운 특성과 많은 수학자들이 그것에 대해 생각하지 않기를 원했다는 사실을 모두 반영했습니다. 그들은 해결할 수 없는 매혹적인 문제를 쫓다가 몇 년 동안의 경력을 잃을까 걱정했습니다. Gilmer는 2013년 어느 날 Saks의 사무실에 가서 노조 폐쇄 추측을 꺼낸 날을 기억합니다. 과거에 그 문제와 씨름했던 그의 고문은 그를 거의 방 밖으로 내쫓을 뻔했습니다.
“Mike가 말했습니다. 'Justin, 당신은 내가 이 문제에 대해 다시 생각하게 할 것이고 나는 그렇게 하고 싶지 않습니다.'”라고 Gilmer가 말했습니다.
불확실성에 대한 통찰
Rutgers를 방문한 후 Gilmer는 문제가 왜 그렇게 어려운지 이해하려고 노력하면서 문제를 마음 속으로 굴렸습니다. 그는 자신에게 기본적인 사실을 제시했습니다. 100세트의 가족이 있는 경우 4,950개를 선택하고 조합을 취하는 방법은 4,950가지가 있습니다. 그런 다음 그는 스스로에게 질문했습니다. 100개의 서로 다른 조합이 적어도 어느 정도 빈도로 해당 조합에 나타나지 않는 요소가 XNUMX개의 집합으로 다시 매핑되는 것이 어떻게 가능할까요?
그 시점에서도 그는 아직 그것을 몰랐지만 증명을 향해 가는 중이었습니다. 한 쌍의 물체를 무작위로 뽑을 때 예상되는 것에 대해 엄격한 사고 방식을 제공하는 정보 이론의 기술은 그를 그곳으로 데려다 줄 것입니다.
정보이론은 20세기 전반기에 개발되었으며, 가장 유명한 것은 Claude Shannon의 1948년 논문 "의사 소통의 수학적 이론.” 이 논문은 메시지가 정확히 무엇을 말해야 하는지에 대한 불확실성의 양을 기반으로 메시지를 보내는 데 필요한 정보의 양을 계산하는 정확한 방법을 제공했습니다. 이 링크 - 정보와 불확실성 사이 — Shannon의 놀랍고 근본적인 통찰력이었습니다.
장난감 예를 들자면 제가 동전을 다섯 번 던진 후 결과 시퀀스를 여러분에게 보낸다고 가정해 보십시오. 일반 코인이라면 전송하는 데 99비트의 정보가 필요합니다. 그러나 동전이 실린 경우(예를 들어 앞면이 나올 가능성이 1%) 소요되는 시간은 훨씬 적습니다. 예를 들어, 로드된 동전이 다섯 번 모두 앞면이 나오면 XNUMX(단일 정보)을 보내겠다고 미리 동의할 수 있습니다. 그럴 가능성이 매우 높습니다. 편향된 동전 던지기의 결과보다 공정한 동전 던지기의 결과에 더 많은 놀라움이 있고 따라서 더 많은 정보가 있습니다.
같은 생각이 일련의 숫자에 포함된 정보에 적용됩니다. 1,024에서 1까지의 10개 세트와 같이 유니온-클로즈드 세트 패밀리가 있는 경우 무작위로 두 세트를 선택할 수 있습니다. 그러면 각 세트의 요소를 여러분에게 전달할 수 있습니다. 해당 메시지를 보내는 데 필요한 정보의 양은 해당 요소가 무엇인지에 대한 불확실성의 양을 반영합니다. 예를 들어 첫 번째 집합의 첫 번째 요소가 50일 가능성이 1%입니다( 공정한 동전 던지기의 첫 번째 결과는 앞면일 확률이 1%인 것과 같습니다.
정보 이론은 길머가 대학원생 때 공부한 대상의 수를 세는 것과 관련된 수학 분야인 조합론에서 자주 나타납니다. 그러나 그가 캘리포니아로 돌아가면서 그는 정보 이론을 폐쇄형 추측에 연결하는 방식이 아마추어의 순진한 통찰력이라고 걱정했습니다. 확실히 일하는 수학자들은 전에 이 반짝이는 물체를 발견했고 그것을 바보의 금으로 인식했습니다. .
Gilmer는 “솔직히 말해서 전에는 아무도 이런 생각을 하지 않았다는 사실에 조금 놀랐습니다. "하지만 XNUMX년 동안 그것에 대해 생각했고 정보 이론을 알고 있었기 때문에 놀라지 말아야 할 것 같습니다."
아닌 것보다 가능성이 더 높음
Gilmer는 Google에서 작업을 마친 후 밤에 문제를 해결했으며 XNUMX월 하반기와 XNUMX월 초에는 주말에 작업했습니다. 그는 한 수학자 그룹이 몇 년 전 한 연구에서 탐구한 아이디어에 고무되었습니다. 열린 협업 Tim Gowers라는 저명한 수학자 블로그에서. 그는 또한 자신이 잊어버린 공식을 찾아볼 수 있도록 교과서를 옆에 놓고 작업했습니다.
“훌륭한 결과를 내놓는 사람이 2장을 참조할 필요가 없다고 생각할 것입니다. 정보 이론의 요소, 하지만 난 그랬어.” 길머가 말했다.
Gilmer의 전략은 모든 집합의 1%에도 요소가 나타나지 않는 조합 폐쇄 가족을 상상하는 것이었습니다. 실제로 존재한다면 Frankl의 추측을 반증하는 반례입니다.
이 집합에서 A와 B라는 두 집합을 무작위로 선택하고 해당 집합에 포함될 수 있는 요소를 한 번에 하나씩 고려한다고 가정해 보겠습니다. 이제 질문하십시오. 세트 A에 숫자 1이 포함될 확률은 얼마입니까? 그리고 B세트? 모든 요소는 주어진 집합에 나타날 확률이 1% 미만이므로 A나 B가 1을 포함할 것이라고 기대하지 않을 것입니다. 즉, 사실 어느 쪽도 아니라는 사실을 알게 되더라도 놀라울 일이 거의 없고 얻을 수 있는 정보도 거의 없습니다. 하다.
다음으로, A와 B의 합집합이 1을 포함할 확률에 대해 생각해 보십시오. 여전히 그럴 가능성은 없지만 개별 집합 중 하나에 나타날 확률보다 가능성이 높습니다. A에 나타날 확률과 B에 나타날 확률의 합에서 둘 다에 나타날 확률을 뺀 값입니다. 그래서 아마도 2% 미만일 것입니다.
이것은 여전히 낮지 만 50-50 명제에 가깝습니다. 즉, 결과를 공유하려면 더 많은 정보가 필요합니다. 다시 말해, 모든 집합의 1% 이상에 요소가 나타나지 않는 Union-closed family가 있는 경우 집합 자체보다 두 집합의 합집합에 더 많은 정보가 있습니다.
“요소별로 사물을 드러내고 학습한 정보의 양을 살펴보는 아이디어는 매우 영리합니다. 그것이 증거의 주요 아이디어입니다.”라고 말했습니다. 라이언 알바이스 프린스턴 대학교.
이 시점에서 Gilmer는 Frankl의 추측에 접근하기 시작했습니다. 그것은 폐쇄형 가족에서 두 집합의 합집합이 반드시 집합 자체보다 더 적은 정보를 포함한다는 것을 쉽게 증명할 수 있기 때문입니다.
그 이유를 알아보기 위해 1,024에서 1까지 만들 수 있는 10개의 서로 다른 집합을 포함하는 폐쇄형 패밀리를 생각해 보십시오. 이러한 집합 중 두 개를 임의로 선택하면 평균적으로 다섯 개의 요소를 포함하는 집합이 됩니다. (이 1,024개의 집합 중 252개는 120개의 요소를 포함하므로 가장 일반적인 집합 크기입니다.) 또한 약 XNUMX개의 요소를 포함하는 공용 구조체로 끝날 가능성이 높습니다. 그러나 XNUMX개의 요소를 포함하는 집합을 만드는 방법은 XNUMX가지에 불과합니다.
요점은 무작위로 선택된 두 집합의 내용에 대한 합집합보다 더 많은 불확실성이 있다는 것입니다. 합집합은 가능성이 더 적은 더 많은 요소가 포함된 더 큰 세트로 기울어집니다. Union-closed family에서 두 세트의 합집합을 취하면 편향된 동전을 던질 때와 같이 무엇을 얻게 될지 알 수 있습니다.
그것으로 Gilmer는 증거를 얻었습니다. 그는 세트의 1%에도 요소가 나타나지 않으면 합집합에 더 많은 정보를 포함해야 한다는 것을 알고 있었습니다. 그러나 합집합은 더 적은 정보를 포함해야 합니다. 따라서 세트의 1% 이상에 나타나는 요소가 하나 이상 있어야 합니다.
푸시 투 50
Gilmer가 16월 38일에 자신의 증명을 게시했을 때 그는 자신의 방법을 사용하여 전체 추측의 증명에 훨씬 더 가까워지고 잠재적으로 임계값을 XNUMX%로 높이는 것이 가능하다고 생각한다는 메모를 포함했습니다.
XNUMX일 후, 세 다른 그룹 의 수학자들이 서로 몇 시간 내에 길머의 작업을 기반으로 한 논문을 게시했습니다. 추가 서류 다음에, 그러나 초기 폭발은 가능한 한 Gilmer의 방법을 취한 것으로 보입니다. 50%에 도달하려면 추가로 새로운 아이디어가 필요합니다.
그럼에도 불구하고 후속 논문의 저자 중 일부는 38%에 도달하는 것이 상대적으로 간단했으며 Gilmer가 직접 수행하지 않은 이유를 궁금해했습니다. 가장 간단한 설명은 올바른 것으로 판명되었습니다. 길머는 수학을 배운 지 XNUMX년이 넘었지만 수학을 해내는 데 필요한 일부 기술 분석 작업을 수행하는 방법을 알지 못했습니다.
"나는 약간 녹슬었고 솔직히 말하면 막혔습니다. "라고 Gilmer는 말했습니다. "그러나 나는 커뮤니티가 그것을 어디로 가져갈지 보고 싶었습니다."
그러나 Gilmer는 자신을 실무에서 제외시킨 동일한 상황이 아마도 처음부터 그의 증명을 가능하게 했다고 생각합니다.
그는 “내가 대학원에서 XNUMX년 동안 그 문제에 대해 생각했지만 진척이 없었고, XNUMX년 동안 수학을 떠났다가 다시 문제로 돌아와 이 돌파구를 만든 이유를 설명할 수 있는 유일한 방법”이라고 말했다. "머신 러닝에 편향된 내 생각을 제외하고는 설명하는 방법을 모르겠습니다."
보정: 2023 년 1 월 3 일
원래 제목은 Gilmer를 "Google 엔지니어"라고 했습니다. 사실 그는 연구원입니다.
