Possible Sizes of Sumsets

당신이 오직 정수(whole numbers)라는 재료만을 가진 주방의 요리사라고 상상해 보십시오. 당신에게는 특정한 레시피가 있습니다: 이 숫자들을 한 움큼 집어 들고, 가능한 모든 방식으로 서로 섞은 뒤, 만들어낼 수 있는 고유한 '총합의 맛(total flavors)'이 몇 개인지 세는 것입니다. 이것은 숫자들이 더해질 때 어떻게 행동하는지를 연구하는 수학의 한 분야인 가법 조합론(additive combinatorics)의 세계입니다. 핵심 질문은 간단하지만 까다롭습니다: 만약 당신이 특정 개수의 재료, 예를 들어 $k$개를 골랐을 때, 이를 $h$번씩 섞는다면 얼마나 다른 결과물들을 얻을 수 있을까요?

블록 쌓기 게임이라고 생각해보십시오. 만약 당신이 작고 깔끔하게 쌓인 블록 뭉치(등차수열)를 가지고 있다면, 그것들을 더했을 때 결과는 예측 가능하고 조밀한 군집을 이룹니다. 하지만 만약 당신이 블록들을 멀리 흩뿌려 놓는다면(예를 들어 2의 거듭제곱처럼), 그 결과는 거대하고 희소한 풍경으로 폭발하듯 넓어집니다. 수학자들은 이 결과물 군집의 '크기'가 될 수 있는 모든 가능성이 무엇인지 오랫동안 궁금해해 왔습니다. 우리가 가진 블록들의 조합으로 만들 수 있는 모든 숫자 사이의 값을 가질 수 있을까요, 아니면 어떤 조합의 블록도 결코 도달할 수 없는 '금지된 간격'이 존재할까요?

Isaac Rajagopal가 작성한 이 논문은 이 퍼즐을 깊이 있게 파고듭니다. 이 논문은 특정한 규칙에 초점을 맞춥니다: 당신은 $k$개의 정수 집합을 가지고 있으며, 이들을 $h$번 더하고자 합니다(이때 같은 숫자를 여러 번 다시 사용할 수 있습니다). 저자는 대부분의 큰 집합에 대해, 이 합집합의 크기가 거의 완벽하고 끊김 없는 선을 형성하며, 오직 몇 가지 특정한, 예측 가능한 구멍들만을 가진다는 것을 증명합니다. 하지만 이 논문은 또한 특정하거나 작은 조합의 경우, 어떤 방식으로 블록을 배치하더라도 절대로 도 साथ 도달할 수 없는 특정 영역이 존재함을 보여줍니다.

위대한 합집합 탐색 (The Great Sumset Hunt)

당신에게 $k$개의 서로 다른 정수가 담긴 가방이 있다고 가정해 봅시다. 당신은 게임을 하기로 합니다: 가방에서 $h$개의 숫자를 뽑고(같은 숫자를 여러 번 뽑을 수 있습니다), 그 숫자들을 모두 더한 뒤, 그 합계를 적습니다. 만약 당신이 가능한 모든 조합에 대해 이 과정을 수행한다면, 당신은 새로운 숫자 리스트를 얻게 됩니다. 이 새로운 리스트의 '크기'는 그 리스트에 포함된 고유한 숫자의 개수입니다.

수학자들은 이 새로운 리스트를 **$h$-fold sumset($h$-중 합집합)**이라고 부릅니다. 거대한 질문은 이것입니다: 만약 재료의 개수($k$)와 섞는 횟수($h$)를 고정한다면, 이 새로운 리스트가 가질 수 있는 모든 가능한 크기는 무엇일까요?

오랫동안 우리는 절대적인 최소값과 최대값을 알고 있었습니다. 최소값은 당신의 숫자들이 $1, 2, 3, 4$처럼 촘촘하게 모여 있을 때 발생합니다. 최대값은 숫자들이$1, 2, 4, 8$처럼 기하급수적으로 퍼져 있을 때 발생합니다. 하지만 그 사이의 값들은 어떠할까요? 우리는 최소와 최대 사이의 모든 숫자를 얻을 수 있을까요, 아니면 결코 존재할 수 없는 '유령 숫자(ghost numbers)'들이 존재할까요?

금지된 삼각형 (The Forbidden Triangle)

논문은 알려진 사실 하나를 확인하며 시작합니다: 어떤 숫자는 얻는 것이 불가능합니다. 당신의 숫자 가방의 크기($k$)를 가로축으로, 숫자를 섞는 횟수($h$)를 세로축으로 하는 그래프를 그린다고 상상해 보십시오. 저자는 $\Delta_{h,k}$(델타라고 읽음)라고 불리는 특정한 모양을 정의합니다.

$\Delta_{h,k}$를 가능성의 지도 위에 그려진 '금지된 삼각형'이라고 생각해 보십시오. 이 논문은 다음과 같은 엄격한 규칙을 증명합니다: 당신이 숫자를 어떻게 배치하든, 합집합의 크기는 결코 이 삼각형 안에 들어올 수 없습니다.

예를 들어, 7개의 숫자가 있고 이를 6번 섞는다면, 크기에 대한 특정한 범위가 완전히 비어 있게 됩니다. 당신은 합집합의 크기로 37을 얻을 수도 있고 924를 얻을 수도 있지만, 만약 그 숫자들이 이 금지된 구역 안에 있다면 40, 41, 또는 42라는 합집합의 크기는 가질 수 없습니다. 이 논문은 집합의 '지름(diameter, 가장 작은 수와 가장 큰 수 사이의 거리)'을 이용한 영리한 트릭을 사용하여 이를 증명합니다. 숫자들이 너무 가까우면 합은 너무 작아지고, 숫자들이 너무 멀리 떨어져 있으면 합은 너무 커집니다. '금지된 삼각형'은 결코 도달할 수 없는 어색한 중간 지점입니다.

간격을 채우기 (거의 다) (Filling the Gaps (Mostly))

이 논문의 주요 발견은 이 금지된 삼각형 외부에서 일어나는 일입니다. 저자는 만약 당신의 숫자 가방이 충분히 크다면(구체적으로 $k$가 $h$에 의존하는 특정 상수보다 크다면), 최소 크기와 최대 크기 사이의 모든 숫자가 가능하다는 것을 증명합니다. 단, 금지된 삼각형 안에 있는 숫자들은 제외입니다.

이것은 마치 양동이에 물을 채우는 것과 같습니다. 당신은 바닥 부분(금지된 삼각형)을 채울 수 없다는 것을 알고 있지만, 일단 그 부분을 지나면, 방금 전의 삼각형 바로 위부터 끝까지 원하는 어떤 높이로든 양동이를 채울 수 있습니다. 다른 신비로운 간격은 없습니다.

이 논문은 매우 영리한 비구성적(non-constructive) 방법을 사용하여 이를 증명합니다. 모든 가능한 크기에 대한 특정 집합을 일일이 만드는 대신(그것은 영원히 걸릴 일입니다), 저자는 집합을 생성하는 '기계'를 만듭니다. 이 기계의 설정을 미세하게 조정함으로써, 결과로 나오는 합집합의 크기는 부드럽게 변합니다. 변화가 부드럽고 연속적이기 때문에, 기계는 반드시 범위 내의 모든 정수 값을 통과해야만 합니다. 이것은 다이얼을 돌리는 것과 같습니다: 각 눈금이 정확히 어디에 있는지 알 필요는 없습니다. 단지 다이얼이 시작부터 끝까지 부드럽게 움직인다는 것만 알면, 그 사이의 모든 숫자를 반드시 지나게 된다는 것을 알 수 있습니다. 결정적으로, 이 증명은 모든 크기에 대해 집합이 존재함을 보장하지만, 어떤 집합이 그 특정한 크기를 만들어내는지 정확히 알려주지는 않습니다.

3의 특별한 경우 (The Special Case of Three)

이 논문은 또한 숫자를 3번 섞는($h=3$) 경우에 대한 오래된 퍼즐을 해결합니다. 여기서 저자는 모든 범위를 얻기 위해 아주 큰 숫자 가방이 필요하지 않다는 것을 증명합니다. 만약 당신이 2개보다 많은 숫자($k > 2$)를 가지고 있다면, 단 하나의 특정한 '유령 숫자'인 $3k - 1$을 제외한 모든 가능한 합집합 크기를 얻을 수 있습니다.

예를 들어, 5개의 숫자가 있고 이를 3번 섞는다면, 가능한 크기는 최소값부터 최대값까지의 모든 숫자이지만, 14라는 숫자 하나는 제외됩니다. 당신은 13을 얻을 수 있고 15도 얻을 수 있지만, 14는 불가능합니다. 이것은 이 특정한 시나리오에 대한 완전하고 정확한 답입니다.

여전히 남아있는 미스터리 (What's Still a Mystery?)

이 논문은 큰 집합들과 $h=3$인 특정한 경우에 대해서는 문제를 해결했지만, 몇 가지 열린 문을 남겨두었습니다. 저자는 이 "삼각형을 제외한 전체 범위" 규칙이, 재료의 개수 $k$가 섞는 횟수 $h$보다 크기만 하다면 더 작은 집합들에 대해서도 적용될 수 있다는 대담한 추측(conjecture)을 제시합니다.

그러나 이 논문은 매우 작은 집합들이거나, 섞는 횟수가 재료의 개수보다 훨씬 많을 때 규칙이 다시 복잡해진다는 점을 인정합니다. 금지된 삼각형 외부에도 우리가 아직 찾아내지 못한 다른 간격들이 존재할 수 있습니다. 또한 저자는 이 문제가 인공지능(구체적으로 증명을 최적화하는 데 ChatGPT의 한 버전이 도움을 주었다고 언급함)을 사용하여 해결될 수 있음을 암시하며, 이 수학의 미래가 인간과 컴퓨터가 완벽한 배치를 찾기 위해 협력하는 방식이 될 것임을 시사합니다.

요약하자면, 이 논문은 "합집합의 우주"에 대한 지도를 그립니다. 그것은 어떤 숫자도 갈 수 없는 금지된 구역을 보여주며, 충분한 재료를 가지고 있다면 그 외의 모든 곳에서 풍경이 연결되어 있고 완전하다는 것을 증명합니다. 이는 혼란스러운 질문을 깨끗하고 예측 가능한 패턴으로 바꾸어 놓았으며, 수학자들이 앞으로도 몇 년 동안 이해하기 위해 노력할 몇몇 신비로운 구멍들만을 남겨두었습니다.