5월 XNUMX일 일요일, Olof Sisask와 Thomas Bloom은 해당 분야에서 가장 큰 미해결 문제에 대한 놀라운 돌파구가 포함된 이메일을 받았습니다. University of Illinois, Urbana-Champaign의 대학원생인 Zander Kelley는 시사스크와 블룸을 보냈습니다. 그가 쓴 논문 UCLA의 Raghu Meka와 함께 로스앤젤레스에 있습니다. Kelley와 Meka는 모두 컴퓨터 과학자였으며 Sisask와 Bloom이 연구하는 덧셈 조합과는 별개의 지적 세계였습니다.

“그냥 마음이 흔들렸어요. 잠깐만 요, 그들이 정말로 이것을 했나요?” 스톡홀름 대학의 강사인 시사스크는 말했다. 조합론 분야의 외부인인 Kelley와 Meka는 정수 집합의 크기에 대해 3개의 간격이 균등하지 않은(8, 13, 101과 같은 조합을 배제하는) 새로운 — 그리고 극적으로 더 낮은 — 한계를 발견했다고 말했습니다. 또는 201, 301 및 XNUMX).

Kelley와 Meka의 주장은 이전 기록을 깨뜨렸습니다. 2020년 달성 옥스포드 대학의 연구원인 Sisask와 Bloom이 작성했습니다. "Bloom과 Sisask의 작업은 매우 강력한 작업이었습니다. 개선하기가 정말 어렵다는 인상을 받았습니다."라고 옥스퍼드에 있는 Bloom's의 동료인 Ben Green은 말했습니다. "그것은 그것이 있던 곳에 아주 붙어 보였다."

Bloom과 Sisask는 모두 이메일을 받았을 때 처리해야 할 다른 긴급한 문제가 있었지만 — Bloom은 방금 강아지를 입양했고 Sisask는 이사하는 중이었습니다. — 그들은 신속하게 새 문서를 확인하는 작업에 착수했습니다.

며칠 안에 Bloom과 Sisask는 새로운 증거가 정확하다고 확신했습니다. 시사스크는 이를 “20년 동안 이 지역에서 가장 큰 성과”라고 불렀다. 다른 사람들이 Kelley와 Meka의 아이디어를 높이 평가하기를 열망하여 그들은 초안을 작성했습니다. 보고서 수학자에게 더 친숙한 용어로 증명을 설명합니다.

Meka는 커뮤니티의 반응이 “생각보다 긍정적이었습니다. 모든 피드백을 보는 것이 놀랍습니다.”

장기간 진행

Kelley와 Meka가 피하려고 했던 균일한 간격의 숫자 시퀀스를 산술 수열이라고 합니다. 그들은 영원히 계속되거나 몇 개의 용어만 포함할 수 있습니다. Kelley와 Meka는 종종 1936 용지 Paul Erdős와 Paul Turán의 작품.

Erdős와 Turán은 천장보다 작은 숫자가 몇 개인지 알고 싶었습니다. N 삼항 산술 진행을 생성하지 않고 집합에 넣을 수 있습니다. N 1,000, 1만 또는 상상할 수 없을 정도로 큰 숫자일 수 있습니다. 그들은 다음과 같이 추측했습니다. N 더 커지면 XNUMX학기 진행이 없는 세트는 엄청나게 희박해져야 합니다. 그런 세트를 만드는 것은 두 켤레가 같은 색상이 아니라고 주장하면서 신발을 수집하는 것과 같습니다. 아마도 영원히 계속할 수 있지만 컬렉션이 커짐에 따라 점점 더 느린 속도로 컬렉션을 추가하게 될 것입니다.

Meka는 “세트를 어떻게 선택하든 관계없이 세트에 등장하는 구조가 있습니다.”라고 설명했습니다. "이 구조가 있다는 것을 보장하기 위해 실제로 얼마나 큰 세트가 필요합니까?"

1946년 펠릭스 베렌트 집합을 구성하는 방법을 찾았습니다. 1과 사이의 숫자 N XNUMX 학기 진행을 생성하지 않고. 그의 방법은 다음과 같이 더 커진 세트를 만들었습니다 N 그랬지만 아프도록 천천히. 언제 N 가 100,000이면 Behrend의 집합에는 171개의 요소만 포함됩니다. 언제 N 그의 집합에는 1개의 숫자가 있습니다. 이는 586백만에서 0.06백만 사이 숫자의 1% 미만입니다.

Behrend의 집합은 수학자에게 작업할 바닥을 제공했습니다. 1953학기 진행이 없는 가장 큰 집합은 적어도 Behrend의 집합만큼 커야 합니다. XNUMX년 클라우스 로스 천장을 제공, 집합이 필연적으로 XNUMX학기 진행을 포함해야 하는 임계값 과거를 찾습니다.

Roth는 Erdős와 Turán의 추측을 증명했습니다. N 더 커지면 1항 진행이 없는 세트는 0.06과 N 사이의 숫자 중 점점 더 작은 부분을 구성하게 됩니다. 그러나 Roth의 천장은 Behrend의 바닥에서 먼 길이었습니다. Behrend는 1만에서 1만 사이의 요소 중 40%가 무진행 세트에 들어갈 수 있음을 보여주었습니다. Roth의 공식은 정확하게 계산하기 어렵지만 그렇게 낮지는 않습니다. 대략적인 추정치에 따르면 백분율을 약 XNUMX%로 제한합니다.

그러나 그 특정 차이보다 더 두드러진 것은 두 공식의 전반적인 동작이었습니다. 1과 XNUMX 사이의 요소 비율을 플로팅합니다. N 그리고 Behrend의 수는 다음과 같이 빠르게 XNUMX으로 줄어듭니다. N 자랍니다. 반면에 Roth의 분수는 XNUMX을 향해 천천히 그리고 부드럽게 미끄러집니다. 두 곡선은 모양이 매우 다르며 수학자들이 알고 있는 한 집합에 있는 요소의 실제 비율은 두 곡선 사이에 있을 수 있습니다.

Green은 1980년대부터 "돌이켜 보면 정말 유명한 수학자들이 상당히 점진적인 개선의 긴 연속 과정을 거쳤습니다."라고 말했습니다. 이따금씩 누군가가 Roth의 상한선을 머리카락 한두 개 아래로 조금씩 밀어냈고 결국 상당히 낮아졌습니다. 대조적으로 Behrend의 하한은 수십 년 동안 움직이지 않았습니다. 수학자들은 Behrend가 정답에서 멀지 않았을 것이라고 생각하기 시작했다고 Bloom은 말했습니다.

Kelley와 Meka의 논문이 2023년 초에 도착할 때까지 무진행 세트의 최대 크기는 아래에서 Behrend의 공식에 의해, 위에서부터 Bloom과 Sisask의 공식에 의해 작성되었습니다. Bloom과 Sisask의 2020년 XNUMX월 논문은 무진행 세트가 N/(통나무 N) 요소. 그러나 그들의 결과는 여전히 Behrend보다 높았습니다. Kelley와 Meka의 새로운 상한은 Behrend가 설정한 바닥에 훨씬 더 가깝습니다.

UCLA의 저명한 수학자 테렌스 타오(Terence Tao)는 “메카와 켈리는 이 모든 점진적인 발전을 뛰어넘었습니다.

그들의 공식은 Behrend의 공식과 거의 동일하며 몇 가지 매개변수만 조정되었습니다. 처럼 N 무한대에 가까워지면 Kelley와 Meka의 공식 플롯은 결국 Behrend 곡선과 유사한 곡선으로 정착됩니다. "그 모양의 경계는 이전에는 불가능한 꿈처럼 보였습니다."라고 Bloom은 말했습니다.

Green은 "그들이 그렇게 개선했다는 사실에 정말 놀랐습니다."라고 말했습니다.

다른 압정

 Kelley와 Meka는 이전에 순수 수학 연구에 완전히 뛰어든 적이 없었지만 처음 시작할 때는 산술 진행이 익숙했습니다. 일반적으로 컴퓨터 과학자들은 "우리의 문제를 해결하는 데 도움이 될 기술을 열심히 찾고 있습니다."라고 Kelley는 말했습니다. 무진행 세트의 크기를 연구하는 데 역사적으로 사용된 도구는 복잡성 이론의 컴퓨터 과학 하위 분야에서 널리 사용되었습니다. 이러한 집합의 크기를 좁히는 문제는 집합의 내부 구조를 조사하는 기술을 적용하는 전형적인 예로서 복잡도 이론가들에게 잘 알려져 있습니다.

2021년 말, Kelley와 Meka는 특정 협력 게임에서 플레이어 팀이 이길 수 있는 확률을 분석하고 있었는데, 이는 표준 유형의 컴퓨터 과학 문제였습니다. 그들은 진행 없는 세트의 크기에 대한 연구에서 얻은 기술이 도움이 될 수 있다는 생각을 했습니다. 그러나 그들은 협동 게임에 적용하는 것보다 이러한 기술을 직접 연구하는 것이 더 쉽다는 것을 알았습니다. Kelley는 "이 문제를 해결하는 방법에 대한 최선의 아이디어는 도구 자체를 실제로 개선하는 것이지 더 영리한 방식으로 사용하는 것이 아닙니다."라고 말했습니다.

Meka는 "어느 시점에서 우리는 이 문제를 직접 해결하기로 결정했습니다."라고 회상했습니다. XNUMX개월 후, 두 연구원은 전략을 알아냈고 그들의 방법을 당면한 문제에 적용하는 방법을 해결해야 했습니다.

새로운 상한선에 어떻게 도달했는지 확인하려면 1과 N. 불러라 A. 밀도 A 1과 사이의 숫자의 백분율입니다. N 포함한다는 것입니다. 1과 XNUMX 사이에는 가능한 많은 수열이 있기 때문에 N, 요소를 선택하지 않으면 A 신중하게, 어떤 A 밀도가 높으면 많은 산술 진행이 포함될 가능성이 높습니다.

증거에서 Kelley와 Meka는 다음과 같이 상상했습니다. A 산술 진행이 거의 또는 전혀 없었으며 결과를 추적하려고 시도했습니다. 만약에 A 충분히 밀도가 높기 때문에 진행이 없으면 내부에 구조 수준이 필요하다는 것을 보여주었습니다. A 그것은 필연적으로 모순을 초래할 것입니다. A 결국 적어도 하나의 진행을 포함해야 합니다.

그 구조를 이해하기 위해 그들은 집합을 고려했습니다. A + A, 의 두 요소를 추가하여 만든 모든 숫자로 구성됩니다. A. 그들은 만약 A 비교적 적은 수의 산술 진행을 포함하며, 이는 요소 간의 중복을 의미합니다. A + A: 서로 다른 숫자 쌍 A 종종 같은 숫자를 더합니다.

밀도는 1과 XNUMX 사이의 모든 정수와 비교하여 정의할 수 있을 뿐만 아니라 N 그러나 일부 하위 집합과 비교하여 해당 간격의 짝수 정수만 말하거나 3의 배수만 말합니다. Kelley와 Meka는 다음에서 중복을 사용했습니다. A + A 의 요소가 있는 정수의 하위 집합을 찾으려면 A 특히 흔했습니다.

예를 들어 A에 3의 배수가 너무 많이 포함되어 있으면 Kelley와 Meka는 3의 배수가 포함된 부분에 집중할 것입니다. 그들은 이 전략을 반복해서 반복했습니다. 그들은 정수의 더 작은 하위 집합을 발견할 때마다 A의 밀도는 계속 성장하고 성장할 것입니다. 예를 들어, A 10과 1 사이의 정수의 XNUMX%를 포함할 수 있습니다. N, 해당 구간에서 15의 배수의 3%, 25의 짝수 배수의 3%.

흥미로운 일이 일어날 때 A 크다. 절차를 반복하면 밀도가 A 일부 하위 집합에서 100%를 초과합니다. 물론 그것은 불가능합니다. A 예를 들어 24의 모든 배수를 포함할 수 있지만 모두 포함할 수는 없습니다. 이 역설은 다음과 같은 경우에만 발생합니다. A 처음에는 충분히 크지만 그렇게 되면 다음과 같은 가정을 의미합니다. A 산술 진행이 포함되어 있지 않습니다.

'윈윈 논쟁'이다. A 크다고 메카는 말했다. 어느 하나 A 많은 산술 진행을 포함하거나 A + A — 이 경우 하위 집합 찾기 절차("밀도 증분 전략"이라고 함)를 사용하여 진행이 다음에 나타나야 함을 보여줄 수 있습니다. A. 밀도 증분 전략은 현장에서 잘 알려진 청사진이지만 Kelley와 Meka는 소규모 A그 어느 때보다. 이를 통해 그들은 진행이 없는 세트의 크기에 대한 새로운 상한선을 발견했습니다.

Kelley와 Meka는 밀도 증분 청사진에서 아이디어의 고유한 조합을 구축했습니다. 그들은 완전히 새로운 프레임워크를 제시하는 대신 밀도가 높은 하위 집합을 찾는 방식을 다시 생각했습니다. 이를 위해 그들은 "체질"이라는 기술을 사용했는데, 이는 세트를 일정한 양만큼 이동하고 교차하고 프로세스를 여러 번 반복하는 것으로 구성됩니다. 여러 라운드의 교차 후에 남아 있는 것은 예측 가능한 속성을 가진 고도로 구조화된 집합입니다. 선별은 다른 논문에서 사용되었지만 XNUMX항 진행 문제에서는 시도된 적이 없습니다.

뒤로보기

Kelley와 Meka는 선별과 같은 방치된 도구를 전통적인 방법에 주입하여 진행이 없는 세트의 크기 제한을 충격적인 양으로 줄였습니다. "Kelley와 Meka는 공개된 곳에 있던 이러한 기술이 우리가 예상했던 것보다 훨씬 더 강력하다는 것을 보여주었습니다." Bloom이 말했습니다. 이러한 도구의 새로운 효능에 비추어 볼 때 그는 "우리는 돌아가서 모든 것을 다시 검토해야 합니다."라고 덧붙였습니다.

밀도 증가 전략은 70년 전 Roth의 논문에 처음 등장했으며 이후 산술 진행에 관한 대부분의 논문에서 사용되었습니다. Green은 프레임워크가 Kelley와 Meka만큼 낮은 범위를 증명하는 데 사용될 수 있다는 사실에 놀랐습니다. "완전하고 근본적으로 다른 것이 필요하다고 생각했습니다."라고 그는 말했습니다.

Kelley는 수학에 대한 그의 진출을 계속하게 되어 기쁩니다. “나는 적어도 이것과 영적으로 관련이 있다고 생각할 수 있는 다양한 문제에 대한 희망과 꿈이 부족하지 않습니다.”라고 그는 말했습니다.

Kelley와 Meka가 한 때 간과되었던 아이디어의 강점을 발견했다는 것은 수학적 진보의 종종 변덕스러운 특성을 보여줍니다. Tao에게는 저주보다 축복에 가까운 품질입니다. "수학이 점점 더 어려워지고 어려워지는 것이 항상 그런 것은 아닙니다."라고 그는 말했습니다. “하느님 감사합니다.”