수학의 'A-팀'은 덧셈과 집합 사이의 중요한 연결을 입증합니다 | 콴타 매거진

무작위로 선택된 숫자 집합에서는 덧셈이 거칠어질 수 있습니다.

그러한 세트의 모든 쌍을 합치면 시작했던 것보다 훨씬 더 많은 숫자를 가질 가능성이 있는 새로운 목록이 생성됩니다. 10개의 난수로 시작하면 이 새 목록(합계 집합이라고 함)에는 약 50개의 요소가 있습니다. 100으로 시작하면 총합은 아마도 약 5,000이 될 것입니다. 1,000개의 임의의 초기 숫자는 500,000개의 숫자 길이를 합산하는 것입니다.

그러나 초기 집합에 구조가 있으면 합계 집합은 이보다 적은 숫자로 끝날 수 있습니다. 또 다른 10개 숫자 집합을 생각해 보세요. 2부터 20까지의 모든 짝수입니다. 서로 다른 쌍의 합이 같은 숫자가 되기 때문에 — 10 + 12는 8 + 14 및 6 + 16과 같습니다 — 합계 집합에는 19개의 숫자만 있고 그렇지 않습니다. 50. 이 차이는 세트가 커질수록 점점 더 심해집니다. 1,000개의 숫자로 구성된 구조화된 목록에는 2,000개의 숫자만 포함된 합계 집합이 있을 수 있습니다.

1960년대에 한 수학자 그레고리 프리먼 가법 조합론의 수학적 분야를 정의하는 중요한 연결인 덧셈과 집합 구조 사이의 연관성을 조사하기 위한 노력의 일환으로 작은 합집합으로 집합을 조사하기 시작했습니다. Freiman은 작은 합집합을 가진 집합이 매우 규칙적인 패턴으로 간격을 두고 있는 요소를 가진 더 큰 집합에 포함되어야 함을 증명하면서 인상적인 진전을 이루었습니다. 그러나 그 분야는 정체되었습니다. “Freiman의 원래 증명은 이해하기가 매우 어려웠으며, 누구도 그것이 정확하다고 절대적으로 확신할 수 없었습니다. 그래서 실제로는 그랬을 수도 있는 영향을 미치지 않았습니다.”라고 말했습니다. 티모시 고워스, Collège de France와 Cambridge University의 수학자이자 필즈 메달리스트입니다. "하지만 임레 루자 현장에 터졌다.”

일련의 두 서류 1990년대에 Ruzsa는 우아한 새로운 주장으로 Freiman의 정리를 다시 증명했습니다. 몇 년 후, 카탈린 마튼2019년에 사망한 헝가리의 영향력 있는 수학자인 는 작은 합집합이 원래 집합의 구조에 대해 무엇을 의미하는지에 대한 질문을 수정했습니다. 그녀는 세트에 등장하는 요소의 유형과 수학자들이 찾아야 할 구조의 유형을 대체하여 수학자들이 더 많은 정보를 추출할 수 있다고 생각했습니다. Marton의 추측은 증명 시스템, 코딩 이론 및 암호화와 관련이 있으며 덧셈 조합론에서 높은 위치를 차지합니다.

그녀의 추측은 “우리가 이해하지 못한 가장 기본적인 것 중 하나처럼 느껴집니다.”라고 말했습니다. 벤 그린, 옥스퍼드 대학교의 수학자. 그것은 "내가 관심을 갖고 있는 많은 것들을 뒷받침해 주었을 뿐입니다."

Green은 Gowers와 힘을 합쳤습니다. 프레디 매너스 캘리포니아대학교 샌디에이고 캠퍼스와 테렌스 타오, 캘리포니아 대학교 로스앤젤레스 캠퍼스의 필즈상 수상자인 이스라엘의 수학자이자 블로거인 길 칼라이 "라고 불렀다.팀"라는 수학자들의 말을 들었습니다. 그들은 논문에서 추측의 버전을 증명했습니다. 9월 XNUMX일에 공유됨.

네츠 카츠연구에 참여하지 않은 라이스 대학의 수학자 는 그 증명이 "아름답고 간단하다"고 설명하며 "거의 완전히 갑자기"라고 설명합니다.

타오는 그 증거를 공식화하기 위한 노력을 시작했습니다. 린, 수학자들이 정리를 검증하는 데 도움이 되는 프로그래밍 언어입니다. 불과 몇 주 만에 그 노력은 성공했습니다. 5월 XNUMX일 화요일 이른 아침, 타오가 발표했다 Lean은 컴퓨터가 특정 단계를 확인할 수 없을 때 나타나는 표준 진술인 "죄송합니다" 없이 추측을 증명했습니다. 이것은 그러한 것의 가장 높은 프로필 사용입니다 2021년부터 검증 도구, 수학자들이 컴퓨터가 이해할 수 있는 용어로 증명을 작성하는 방식에 변곡점을 표시합니다. 이러한 도구가 수학자들이 사용할 수 있을 만큼 쉬워지면 종종 길고 번거로운 동료 검토 프로세스를 대체할 수 있을 것이라고 Gowers는 말했습니다.

증거의 재료는 수십 년 동안 끓였습니다. Gowers는 2000년대 초반에 첫 단계를 구상했습니다. 그러나 Kalai가 현장의 "성배"라고 부르는 것을 증명하는 데는 20년이 걸렸습니다.

그룹 내

마튼의 추측을 이해하려면 집합과 연산으로 구성된 수학적 대상인 군의 개념을 익히는 것이 도움이 됩니다. 무한한 숫자 집합인 정수와 덧셈 연산을 생각해 보세요. 두 개의 정수를 더할 때마다 또 다른 정수를 얻게 됩니다. 덧셈은 연산 순서를 변경할 수 있는 결합성(3 + (5 + 2) = (3 + 5) + 2)과 같은 그룹 연산의 몇 가지 다른 규칙도 따릅니다.

그룹 내에서 모든 그룹 속성을 충족하는 더 작은 집합을 찾을 수 있는 경우가 있습니다. 예를 들어, 짝수 두 개를 더하면 또 다른 짝수를 얻게 됩니다. 짝수는 그 자체로 그룹이므로 정수의 하위 그룹이 됩니다. 대조적으로 홀수는 부분군이 아닙니다. 두 개의 홀수를 더하면 원래 세트에는 없는 짝수를 얻게 됩니다. 하지만 모든 짝수에 1을 더하면 모든 홀수를 얻을 수 있습니다. 이와 같이 이동된 하위 그룹을 코셋(coset)이라고 합니다. 하위 그룹의 모든 속성을 갖지는 않지만 여러 가지 방법으로 하위 그룹의 구조를 유지합니다. 예를 들어, 짝수와 마찬가지로 홀수도 모두 균등한 간격으로 배열되어 있습니다.

Marton은 우리가 호출할 세트가 있으면 가정했습니다. A 그 합계가 다음보다 그다지 크지 않은 그룹 요소로 구성됩니다. A 그 자체이면 일부 하위 그룹이 존재합니다. 이를 호출합니다. G — 특별한 속성이 있습니다. 옮기다 G 몇 번에 걸쳐 세트를 만들면 그 세트에는 원본 세트가 모두 포함됩니다. A. 더욱이 그녀는 coset의 수가 합집합의 크기보다 훨씬 빠르게 증가하지 않는다고 가정했습니다. 그녀는 그것이 훨씬 더 빠른 기하급수적 증가와는 반대로 다항식 요인에 의해 관련되어야 한다고 믿었습니다.

이것은 매우 기술적 호기심처럼 들릴 수도 있습니다. 하지만 이는 간단한 테스트와 관련되어 있기 때문에 세트에 두 개의 요소만 추가하면 어떻게 될까요? — 하위 그룹의 전반적인 구조는 수학자 및 컴퓨터 과학자에게 매우 중요합니다. 컴퓨터 과학자들이 한 번에 메시지의 일부만 해독할 수 있도록 메시지를 암호화하려고 시도할 때도 동일한 일반적인 아이디어가 나타납니다. 이는 또한 컴퓨터 과학자가 몇 ​​가지 고립된 정보 비트만 확인하여 확인할 수 있는 증명 형태인 확률론적으로 확인 가능한 증명에도 나타납니다. 이러한 각 경우에 긴 메시지에서 몇 비트만 디코딩하거나 복잡한 증명의 작은 부분을 확인하는 등 구조의 몇 가지 지점만 사용하여 더 크고 더 높은 수준의 구조에 대한 결론을 내립니다.

"모든 것이 그룹의 큰 부분 집합이라고 가정할 수 있습니다."라고 말했습니다. 톰 샌더스, Gowers의 전 학생이었으며 현재 Oxford에서 Green의 동료가 되었습니다. 또는 “많은 부가적인 우연의 존재로부터 원하는 모든 것을 얻을 수 있습니다. 이 두 가지 관점 모두 유용합니다.”

루자 1999년 마튼의 추측 발표, 그녀에게 전적인 공로를 인정합니다. “그녀는 나와 프레이먼과는 별개로, 아마도 우리보다 먼저 그런 추측을 했을 것입니다.”라고 그는 말했습니다. "그래서 나는 그녀와 이야기를 나눌 때 그것을 그녀의 추측이라고 부르기로 결정했습니다." 그럼에도 불구하고 수학자들은 이제 이를 다항식 Freiman-Ruzsa 추측(PFR)이라고 부릅니다.

XNUMX과 XNUMX

많은 수학적 객체와 마찬가지로 그룹은 다양한 형태를 취합니다. Marton은 자신의 추측이 모든 그룹에 대해 사실이라고 생각했습니다. 아직 표시되지 않았습니다. 새로운 논문은 (0, 1, 1, 1, 0)과 같은 이진수 목록을 요소로 사용하는 특정 종류의 그룹에 대해 이를 증명합니다. 컴퓨터는 바이너리로 작동하기 때문에 이 그룹은 컴퓨터 과학에서 매우 중요합니다. 그러나 이는 덧셈 조합론에도 유용했습니다. 샌더스는 “이것은 놀고 여러 가지를 시도해 볼 수 있는 장난감 환경과 같습니다.”라고 말했습니다. 그는 정수를 다루는 것보다 "대수학이 훨씬 더 좋다"고 덧붙였습니다.

목록의 길이는 고정되어 있으며 각 비트는 0 또는 1이 될 수 있습니다. 1 + 1 = 0이라는 규칙을 사용하여 각 항목을 다른 목록의 해당 항목에 추가하여 함께 추가합니다. 따라서 (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR은 집합이 하위 그룹은 아니지만 그룹과 유사한 특징을 갖고 있는 경우 집합이 어떤 모습일 수 있는지 알아내려는 시도입니다.

PFR을 정확하게 만들기 위해 다음과 같은 이진 목록 집합이 있다고 상상해 보십시오. A. 이제 모든 요소 쌍을 가져옵니다. A 그리고 그것들을 더하세요. 결과 합계는 다음의 합계를 구성합니다. A라는 A + A. 의 요소라면 A 무작위로 선택되면 대부분의 합계가 서로 다릅니다. 만일 거기에 k 요소 A, 그 말은 주변에 있을 것이라는 뜻이에요 k²/2개의 요소가 합집합에 포함됩니다. 언제 k 크다 - 예를 들어 1,000 - k²/2는 다음보다 훨씬 큽니다. k. 하지만 A 하위 그룹, 모든 요소는 A + A 에 A, 그 의미 A + A 와 크기가 같다 A 자체.

PFR은 무작위가 아니지만 부분군도 아닌 집합을 고려합니다. 이 세트에서 요소의 수는 A + A 다소 작습니다 - 예를 들어 10k또는 100k. "단순히 정확한 대수적 구조를 갖는 것보다 구조에 대한 개념이 훨씬 더 풍부할 때 정말 유용합니다."라고 말했습니다. 샤차르 로베트, 캘리포니아 대학교 샌디에고 캠퍼스의 컴퓨터 과학자입니다.

Tao는 수학자들이 이 속성을 따르는 것으로 알고 있는 모든 집합이 "실제 하위 그룹과 매우 유사"하다고 말했습니다. "그것은 다른 종류의 가짜 그룹이 주변에 존재하지 않는다는 직관이었습니다." Freiman은 그의 원본 연구에서 이 진술의 버전을 증명했습니다. 1999년에 Ruzsa는 Freiman의 정리를 정수에서 이진 목록 설정으로 확장했습니다. 그는 증명했다 그 때 요소의 수는 A + A 는 크기의 상수 배수이다. A, A 하위 그룹 내에 포함되어 있습니다.

그러나 Ruzsa의 정리는 부분군이 거대해야 함을 요구합니다. Marton의 통찰력은 하나의 거대한 하위 그룹에 포함되기보다는 A 원래 세트보다 크지 않은 하위 그룹의 다항식 수의 coset에 포함될 수 있습니다. A.

'나는 진짜 아이디어를 보면 진짜 아이디어를 안다'

새천년이 시작될 무렵, Gowers는 균일한 간격의 숫자로 구성된 문자열을 포함하는 집합에 관한 다른 문제를 연구하던 중 Ruzsa의 Freiman 정리 증명을 접하게 되었습니다. Gowers는 "특정 세트에 대한 훨씬 느슨한 정보에서 구조적 정보를 얻는 것과 같은 것이 필요했습니다."라고 말했습니다. "얼마 전에 Ruzsa가 정말 멋진 증거를 제시했다는 것은 정말 행운이었습니다."

Gowers는 추측의 다항식 버전에 대한 잠재적인 증거를 찾기 시작했습니다. 그의 아이디어는 세트로 시작하는 것이었습니다 A 그 합계는 상대적으로 작았고 점차적으로 조작했습니다. A 하위 그룹으로. 결과 하위 그룹이 원래 세트와 유사하다는 것을 증명할 수 있다면 A, 그는 그 추측이 사실이라고 쉽게 결론을 내릴 수 있었습니다. Gowers는 자신의 아이디어를 동료들과 공유했지만 누구도 이를 완전한 증거로 만들 수 없었습니다. Gowers의 전략은 어떤 ​​경우에는 성공했지만 다른 경우에는 조작이 필요했습니다. A 다항식 Freiman-Ruzsa 추측의 원하는 결론에서 더 멀리 떨어져 있습니다.

결국 현장은 계속 진행됐다. 2012년 샌더스는 거의 입증된 PFR. 그러나 그에게 필요한 이동된 하위 그룹의 수는 비록 약간이지만 다항식 수준보다 높았습니다. Gowers는 "그가 그렇게 한 후에는 덜 시급한 일이 되었지만 여전히 내가 매우 좋아하는 정말 좋은 문제가 되었음을 의미했습니다."라고 말했습니다.

그러나 Gowers의 아이디어는 동료들의 기억과 하드 드라이브에 남아 있었습니다. Gowers의 학생이기도 한 Green은 “거기에 진짜 아이디어가 있습니다.”라고 말했습니다. “나는 진짜 아이디어를 보면 진짜 아이디어를 안다.” 이번 여름, Green, Manners 및 Tao는 마침내 Gowers의 아이디어를 연옥에서 해방시켰습니다.

Green, Tao 및 Manners는 Gowers의 37년 된 아이디어로 돌아가려고 생각하기 전에 20페이지에 걸쳐 협력했습니다. 23월 XNUMX일에 종이, 그들은 작은 합집합으로 집합의 구조를 조사하기 위해 확률 변수라는 확률 이론의 개념을 성공적으로 사용했습니다. 이러한 전환을 통해 그룹은 세트를 더욱 정교하게 조작할 수 있었습니다. Manners는 “무작위 변수를 다루는 것은 집합을 다루는 것보다 훨씬 덜 엄격합니다.”라고 말했습니다. 무작위 변수를 사용하면 "확률 중 하나를 조금씩 조정할 수 있으며, 그러면 더 나은 무작위 변수가 제공될 수 있습니다."

이러한 확률론적 관점을 사용하여 Green, Manners 및 Tao는 세트의 요소 수를 다루는 작업에서 엔트로피라는 수량인 무작위 변수에 포함된 정보를 측정하는 작업으로 이동할 수 있습니다. 엔트로피는 덧셈 조합론에 새로운 것이 아니었습니다. 사실 타오는 시도했다 2000년대 후반에 이 개념이 대중화되었습니다. 그러나 아직 다항식 Freiman-Ruzsa 추측에 그것을 사용하려고 시도한 사람은 아무도 없었습니다. Green, Manners 및 Tao는 그것이 강력하다는 것을 발견했습니다. 그러나 그들은 여전히 ​​그 추측을 증명할 수 없었습니다.

그룹은 새로운 결과를 검토하면서 마침내 Gowers의 휴면 아이디어가 번성할 수 있는 환경을 구축했다는 것을 깨달았습니다. 요소 수보다는 엔트로피를 사용하여 세트의 크기를 측정하면 기술적 세부 사항이 훨씬 더 잘 작동할 수 있습니다. Tao는 "어느 시점에서 우리는 20년 전 Tim의 오래된 아이디어가 실제로 우리가 시도했던 것보다 더 효과가 있을 가능성이 높다는 것을 깨달았습니다."라고 말했습니다. “그래서 우리는 Tim을 다시 프로젝트에 참여시켰습니다. 그러면 모든 조각이 놀라울 정도로 잘 맞아떨어지죠.”

하지만 증거가 완성되기 전에 알아내야 할 세부 사항이 많이 있었습니다. 매너스는 “우리 넷 모두가 다른 일로 엄청나게 바쁘다는 것은 좀 어리석은 일이었다”고 말했다. "이 훌륭한 결과를 발표하고 세상에 알리고 싶지만 실제로는 여전히 중간고사를 작성해야 합니다." 결국 그룹은 끝까지 밀어붙였고 9월 XNUMX일에 논문을 게재했습니다. 그들은 만약에 A + A 다음보다 크지 않다 k 크기의 배 A다음, A 대략적으로만 커버할 수 있습니다. k¹² 다음보다 크지 않은 부분군의 이동 A. 이는 잠재적으로 엄청난 교대 횟수입니다. 그러나 이는 다항식이므로 다음과 같이 기하급수적으로 빠르게 증가하지 않습니다. k 점점 커지는 것 같아 k 지수에 있었어요.

며칠 후, 타오 시작했다 증거를 공식화하십시오. 그는 버전 제어 패키지 GitHub를 사용하여 공동으로 공식화 프로젝트를 실행하여 다음의 기여를 조정했습니다. 전 세계 25명의 자원봉사자. 그들은 다음과 같은 도구를 사용했습니다. 청사진 에 의해 개발 패트릭 마쏘파리-사클레 대학의 수학자인 타오(Tao)에서 번역하려는 노력을 조직했습니다. 라는 "수학 영어"를 컴퓨터 코드로 변환합니다. Blueprint는 무엇보다도 차트 증명과 관련된 다양한 논리적 단계를 묘사합니다. 모든 거품이 Tao가 "사랑스러운 녹색 음영"이라고 부르는 것으로 덮이면 팀이 완성되었습니다. 그들은 온라인 신문에서 몇 가지 아주 사소한 오타를 발견했습니다. 메시지, Tao는 "프로젝트에서 수학적으로 가장 흥미로운 부분은 공식화하기가 상대적으로 간단했지만 기술적으로 '명백한' 단계에 가장 오랜 시간이 걸렸습니다."라고 언급했습니다.

Marton은 그녀의 유명한 추측이 증명되기 불과 ​​몇 년 전에 사망했지만 그 증거는 그녀를 반영합니다. 인생의 일 엔트로피와 정보 이론. Gowers는 “내가 하려고 했던 프레임워크에서보다 이 엔트로피 프레임워크에서 수행할 때 모든 것이 훨씬 더 잘 작동합니다.”라고 말했습니다. "나에게는 아직도 그것이 다소 마법처럼 느껴집니다."

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 수학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 판매