낮에는 일하고 밤에는 연구를 수행하는 Google Brain 연구 과학자들은 수십 년 동안 수학계를 곤혹스럽게 만들었던 추측을 풀었습니다.

2022년 10월 중순, 저스틴 길머는 동부 해안에 있는 러트거스 대학의 수학자이자 전 멘토였던 마이클 삭스를 만나기 위해 캘리포니아에서 뉴욕으로 날아갔습니다.

회상하는 동안 그들은 수학에 대해 이야기하지 않았습니다. 실제로 길머는 2015년 러트거스 대학교에서 박사 학위를 취득한 이후로 수학에 대해 진지하게 생각해 본 적이 없습니다. 그 당시 그는 학계에서 경력을 쌓지 않기로 결정하고 프로그래밍을 독학하기 시작했습니다. Saks와 저녁 식사를 하면서 Gilmer는 멘토에게 Google에서 하는 일, 즉 기계 학습과 인공 지능에 대해 이야기했습니다.

길머는 캠퍼스 길을 걷던 중 2013년에 "Union Closed Set Conjecture(프랭클 추측이라고도 함)"라는 문제를 생각하며 이 길을 걷는 데 1년이 넘는 시간을 보냈다고 회상했습니다. 이것은 언제나 쓸데없는 문제였습니다. 그의 모든 노력에도 불구하고 Gilmer는 숫자 모음에 관한 겉보기에 단순해 보이는 이 문제가 해결하기 어려운 이유를 스스로 가르치는 데 성공했습니다.

그러나 7년 후, 이번 방문 이후 길머는 갑자기 새로운 영감을 얻었습니다. 그는 집합 추측을 풀고 마무리하기 위해 정보 이론을 적용하는 방법에 대해 생각하기 시작했습니다. 한 달 간의 연구 끝에 증거를 향한 길이 계속 열렸습니다. 11월에 그는 arXiv에 결과를 게시하여 전체 추측을 입증하는 데 상당한 진전이 있음을 발표했습니다.

논문 링크: https://arxiv.org/pdf/2211.09055.pdf

이 논문은 후속 연구의 물결을 촉발시켰습니다. 옥스퍼드 대학교, MIT 및 고등연구소의 수학자들은 신속하게 길머의 새로운 방법에 대한 연구를 시작했습니다.

합집합 폐쇄집합 추측이란 무엇인가요?

닫힌 집합 추측은 {1, 2} 및 {2, 3, 4}와 같은 숫자 집합과 관련이 있습니다. 집합을 병합하는 합집합을 포함하여 집합에 대한 작업을 수행할 수 있습니다. 예를 들어, {1, 2}와 {2, 3, 4}의 합집합은 {1, 2, 3, 4}입니다.

패밀리에 있는 두 세트의 합집합이 해당 패밀리에 있는 기존 세트와 같을 경우 세트 또는 패밀리를 "결합 폐쇄"라고 합니다. 예를 들어, {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}의 4개 집합 계열을 생각해 보세요.

어떤 쌍이든 결합하면 해당 패밀리에 이미 존재하는 세트를 얻게 되므로 이 패밀리를 닫힌 세트라고 합니다.

수학자들은 집합 추측에 대해 이미 1960년대부터 논의하고 종결했지만, 1979년이 되어서야 이 집합 추측에 대한 최초의 공식 성명이 발표되었습니다. 헝가리 수학자 피터 프랭클은 1980년대에 일본으로 이주했습니다. 그는 수학 외에도 거리 공연도 좋아합니다.

프랭클은 집합군이 폐쇄형 집합이라면 적어도 집합의 절반에 나타나는 요소(또는 숫자)가 하나 이상 있어야 한다고 추측했습니다. 이는 두 가지 이유로 인해 자연적으로 발생하는 임계값입니다.

​

Justin Gilmer

첫째, 모든 요소가 집합의 정확히 50%에 나타나는 기성 집합 집합의 폐쇄형 집합의 예입니다. 예를 들어, 1부터 10까지의 숫자를 사용하여 모든 다른 세트를 구성하면 총 1024개의 세트가 생성될 수 있습니다. 그들은 10개의 요소 각각이 나타나는 512개 세트의 닫힌 계열을 형성합니다.

프랭클이 이 추측을 제안했을 때, 그 추측이 유효하지 않은 닫힌 집합의 예를 제안한 사람은 아직 아무도 없었습니다. 따라서 50%는 올바른 예측인 것 같습니다.

그렇다고 증명하기 쉽다는 뜻은 아닙니다. Gilmer의 작업 이전에는 많은 논문에서 모든 크기의 세트 패밀리에 대해 동일한 50% 임계값이 아니라 패밀리의 세트 수에 따라 달라지는 임계값만 설정했습니다.

Columbia University의 Will Sawin은 "쉬워야 할 것 같고 많은 쉬운 문제와 비슷하지만 결코 정복된 적이 없습니다."라고 말했습니다.

진행이 부족한 것은 문제의 다루기 힘든 성격과 많은 수학자들이 그것에 대해 생각하지 않는다는 사실을 모두 반영합니다. 그들은 불가능한 문제를 쫓느라 수년간의 경력을 낭비하게 될까 봐 걱정합니다. Gilmer는 2013년의 어느 날을 기억합니다. 그가 Saks의 사무실에 가서 이것과 비공개 추측을 언급했고, 역시 문제와 씨름하던 강사들이 그를 방에서 쫓아냈습니다.

불확실성에 대한 통찰력

Rutgers를 방문한 후 Gilmer는 마음 속으로 질문을 굴려 그것이 왜 그렇게 어려운지 이해하려고 노력했습니다. 그는 기본적인 사실을 스스로 상기시켰습니다. 100개의 세트 조합으로 구성된 가족이 있다면 두 개를 선택하고 조합하는 방법은 4950가지가 있다는 것입니다. 그런 다음 그는 생각했습니다. 적어도 어느 정도 빈도로 이러한 조합에 요소가 나타나지 않으면 어떻게 4950개의 서로 다른 조합이 100개의 세트로 매핑될 수 있습니까?

이 시점에서 그는 아직은 모르지만 이미 결심의 길에 들어서 있습니다.

정보 이론은 20세기 전반에 개발되었으며, 특히 클로드 섀넌(Claude Shannon)의 1948년 논문 "커뮤니케이션의 수학적 이론"에서 가장 두드러지게 나타났습니다. 이 문서에서는 메시지가 표현하는 내용을 둘러싼 불확실성의 양을 기반으로 메시지를 보내는 데 필요한 정보의 양을 계산하는 정확한 방법을 제공합니다. 정보와 불확실성 사이의 이러한 연결은 Shannon의 놀라운 통찰력입니다.

정보 이론은 길머가 대학원생 때 공부했던 사물의 세기와 관련된 수학 분야인 조합론에 자주 등장합니다. 그러나 캘리포니아로 돌아오면서 그는 정보 이론을 통합 폐쇄 집합 추측과 연관시키는 방식이 아마추어의 순진함을 걱정했습니다.

"솔직히 말해서 이전에 아무도 이런 생각을 해본 적이 없다는 사실에 조금 놀랐습니다." 길머가 말했습니다. "하지만 놀라지 않아도 될 것 같습니다. 왜냐하면 나 자신이 1년 동안 그것에 대해 생각해왔고 정보 이론을 이해했기 때문입니다."

어려운 문제 탐구

Gilmer의 수학 연구는 수학에 대한 사랑에서 비롯되었습니다. 주로 평일에는 구글에서의 일상 업무로 바쁘고, 여가 시간에는 수학 문제를 공부하는 데 전념합니다. 그는 또한 수학 교과서를 가지고 출근하여 잊어버린 공식을 언제든지 찾아볼 수 있습니다. Gilmer는 땅에 발을 딛고 별을 바라보기도 합니다. 그는 그에게 영감을 주는 유명한 수학자 Tim Gowers의 블로그를 읽는 것을 좋아합니다.

Gilmer는 겸손하게 말했습니다: "수학 문제를 푸는 사람은 "정보 이론의 기본(정보 이론의 기초)" 2장을 참조하면 안 된다고 생각할 수도 있지만 저는 그랬습니다.

Gilmer가 제안한 방법은 다음과 같습니다. 모든 집합에 요소가 나타날 확률이 1% 미만인 폐쇄 집합군을 생각해 보세요. 이것은 만약 사실이라면 프랭클의 추측을 위조하는 반례이다.

두 집합 A와 B가 이 집합에서 무작위로 선택되었다고 가정하고, 집합 A에 숫자 1이 포함될 확률은 얼마입니까? B세트는 어떨까? 특정 세트에 각 요소가 나타날 확률은 1%보다 약간 낮으므로 A 또는 B에 1이 포함될 것이라고 기대해서는 안 됩니다. 이는 둘 다 실제로 1을 포함하지 않더라도 놀라지 않을 것이며 확실히 많은 정보를 얻지 못할 것임을 의미합니다.

다음으로, A와 B의 합집합에 1이 포함될 확률을 생각해 보세요. 이는 여전히 가능성이 낮지만 어느 한 세트에만 1이 나타날 확률보다 약간 더 크며 A에 1이 나타날 확률과 B에 1이 나타날 확률의 합에서 두 세트 모두에 1이 나타날 확률을 뺀 값입니다. 따라서 A와 B의 합집합에 1이 포함될 확률은 약 2% 미만입니다.

이 수치는 여전히 낮지만 50% 추측에 가깝습니다. 즉, 결과를 공유하려면 더 많은 정보가 필요하다는 의미입니다. 즉, 모든 집합에 요소가 나타날 확률이 1% 미만인 집합을 묶는 집합 계열이 있는 경우 두 집합의 합집합에는 두 집합 자체보다 더 많은 정보가 포함됩니다.

프린스턴 대학의 Ryan Alweiss는 "요소별로 추측 요소를 증명하는 아이디어는 매우 영리합니다."라고 말했습니다.

Gilmer의 작업은 Frankl의 추측에 가까워지기 시작했습니다. 이는 공용체 폐쇄 세트 계열에서 두 세트의 합집합이 두 세트 자체보다 더 적은 정보를 포함해야 함을 보여주기 쉽기 때문입니다.

이유는 간단합니다. 1024개의 서로 다른 세트를 포함하는 통합 폐쇄 세트 패밀리를 예로 들면, 각 세트의 요소는 1부터 10까지입니다. 이들 세트 중 2개를 무작위로 선택하면 평균적으로 5개 요소의 합집합이 얻어집니다. (1024개의 세트 중 252개에는 5개의 요소가 포함되어 있으며 이는 가장 일반적인 세트 크기입니다.) 약 7개의 요소의 합집합을 얻는 것도 가능합니다. 그러나 7가지 요소의 합집합을 얻는 방법의 조합은 120가지에 불과합니다.

중요한 점은 무작위로 선택된 두 세트에는 합집합보다 불확실성이 더 큰 요소가 포함되어 있다는 것입니다. 공용체는 더 많은 요소와 더 적은 가능성을 가진 더 큰 집합에 가깝습니다. 집합이 닫힌 집합의 두 집합에 대해 합집합 연산을 수행하면 편향된 동전을 던지는 것처럼 합집합의 결과를 알 수 있습니다. 동전이 어느 쪽에 떨어질지 쉽게 추측할 수 있습니다. 두 세트 자체보다.

이를 바탕으로 Gilmer는 집합에 적어도 하나의 요소가 나타날 확률이 1% 이상이라고 믿습니다.

잃어버린 것, 얻는 것이 있다

Gilmer가 11월 16일에 자신의 증명을 발표했을 때 메모를 첨부했습니다. 그는 자신의 방법을 사용하는 것이 완전한 추측의 증명에 더 가까울 수 있다고 믿었습니다. 기준치가 38%로 높아졌습니다.

5일 후, 세 개의 서로 다른 수학자 그룹이 서로 몇 시간 내에 Gilmer의 작업을 기반으로 한 논문을 발표했습니다. 이번 발병으로 인해 Gilmer의 접근 방식이 극단으로 치닫게 된 것으로 보이지만 50%에 도달하려면 더 많은 새로운 아이디어가 필요할 수 있습니다.

그러나 후속 논문의 일부 저자들은 왜 Gilmer가 상대적으로 간단한 38% 연구를 직접 수행하지 않았는지 궁금해했습니다. 사실 그 이유는 복잡하지 않습니다. 수학에서 5년 이상 떨어져 있던 Gilmer는 이 목표를 달성하기 위해 기술적 분석 작업을 수행하는 방법을 몰랐습니다.

"저는 좀 녹슬었고, 솔직히 막히네요." 길머가 말했습니다. "그러나 나는 수학계가 그것을 어디로 가져갈지 궁금합니다."

그러나 길머는 또한 그에게 그것을 연습할 기회를 잃게 만든 동일한 이유가 부분적으로 그의 증명을 처음에 가능하게 만든 것이라고 믿습니다. place: “ 대학원에서 1년 동안 이 문제에 대해 생각을 하다가 진전이 없었다가 6년 동안 수학을 그만둔 뒤 이 문제로 돌아왔을 때 돌파구를 찾은 이유는 이것뿐이다. 머신러닝 때문에 다른 설명은 모르겠네요.”

위 내용은 낮에는 일하고 밤에는 연구를 수행하는 Google Brain 연구 과학자들은 수십 년 동안 수학계를 곤혹스럽게 만들었던 추측을 풀었습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!