Inverse problems for sumset sizes of finite sets of integers

숫자가 단순히 개수를 세는 도구가 아니라, 서로 어떻게 섞이는지에 대한 이야기를 담은 캐릭터라고 상상해 보세요. 이 이야기는 **가법 정수론(additive number theory)**이라는 수학의 한 분야에 살고 있습니다. 이 분야는 숫자들의 집합을 가져와서 서로 더했을 때 어떤 일이 일어나는지를 연구합니다. 이것을 주방에 비유해 본다면, 만약 당신이 특정한 재료들(숫자들의 집합)이 담긴 봉지를 가지고 있다면, 이들을 섞었을 때 어떤 결과가 나올까요? 두 가지 재료를 결합하면 새로운 배치가 만들어지고, 세 가지를 결합하면 훨씬 더 큰 배치가 만들어집니다. 수학자들은 이러한 배치들을 "합집합(sumsets)"이라고 부릅니다.

이 논문이 다루는 핵심 질문은 마치 탐정 소설과 같습니다. 보통 우리는 재료가 무엇인지 알고 최종 요리의 크기를 예측하려 합니다. 하지만 여기에서의 탐정은 정반대의 문제를 안고 있습니다. 탐정은 요리의 크기가 시간이 지남에 따라 커지는 것을 보고, 원래의 재료가 정확히 무엇이었는지를 알아내고자 합니다. 이 논문은 다음과 같이 묻습니다. 만약 서로 다른 두 그룹의 재료가 모든 조리 단계에서 정확히 같은 크기의 요리를 만들어낸다면, 그 재료들은 실제로 같은 것일까요? 아니 else 완전히 다른 "레시피"(집합)가 동일한 성장 패턴을 만들어낼 수 있을까요? 결과적으로 정수의 세계에서 그 답은 놀라울 정도로 까다로우며, 이 숫자-배치들의 성장은 우리가 이제 겨우 이해하기 시작한 방식으로 꿈틀대고 춤을 출 수 있습니다.

---

커져가는 숫자 더미의 미스터리

이 논문에서 저자인 멜빈 B. 네이선슨(Melvyn B. Nathanson)은 유한 정수 집합의 "합집합 크기(sumset size)"를 조사합니다. 이를 쉬운 비유로 풀어보겠습니다. 당신이 독특한 돌들을 모은 작은 컬렉션, 예를 들어 집합 $A$를 가지고 있다고 상상해 보세요. 만약 이 더미에서 돌 두 개를 꺼내 그 값들을 더하면, '2-중 합집합($2A$)'이라 불리는 새로운 숫자 더미가 생깁니다. 만약 세 개의 돌을 더한다면 '3-중 합집합($3A$)'이 되고, 계속해서 더해 나가는 식입니다. 이 논문은 숫자를 계속 섞을 때 이 더미의 크기(고유한 항목의 개수)가 어떻게 변하는지를 추적합니다.

오랫동안 수학자들은 이 과정을 충분히 반복하다 보면, 더미의 크기가 매우 예측 가능한 직선형 패턴으로 성장한다는 것을 알고 있었습니다. 이는 마치 자동차가 결국 일정한 크루즈 컨트롤 속도로 정속 주행에 들어서는 것과 같습니다. 이 논문은 이러한 "크루즈 컨트롤" 동작을 확인하며, 합집합의 크기가 새로운 층을 더할 때마다 고정된 양만큼 증가하게 된다는 것을 보여줍니다.

위대한 정체성 교체

진정한 마법은 저자가 다음과 같은 질문을 던질 때 일어납니다: 두 개의 서로 다른 숫자 집합이 성장할 때 똑같이 보일 수 있을까?

서로 다른 두 개의 레고 상자가 있다고 상상해 봅시다. 상자 A에는 빨간 벽돌 하나와 파란 벽돌 하나가 있습니다. 상자 B에는 초록색 벽돌 하나와 노란색 벽돌 하나가 있습니다. 만약 이 벽돌들을 쌓아서 탑을 만든다면, 두 상자에서 만들 수 있는 고유한 탑 높이의 개수가 동일할 수도 있습니다. 이 논문은 이것이 단순한 우연이 아니라, 특정 크기를 가진 집합들에게 흔히 일어나는 현상임을 증명합니다.

저자는 "아핀 불변(affinely inequivalent)"인 구체적인 예시들을 구성합니다. 쉽게 말해, 이는 단순히 서로를 복사한 형태(예를 들어 모든 숫자를 1만큼 올리거나 2배로 늘린 형태)가 아닌, 진정으로 다른 모양을 가진 집합들을 의미합니다. 논문은 집합의 크기가 $k \ge 3$일 때, 모든 단계 $h=2$부터 ($h=2, 3, 4, \dots$) 합집합의 항목 수가 동일한 서로 다른 집합 쌍을 찾을 수 있음을 보여줍니다.

예를 들어, 이 논문은 크기가 3인 두 집합을 명시적으로 구성합니다:

• 집합 A: $\{0, 2, 7\}$
• 집합 B: $\{0, 3, 7\}$

이 집합들은 서로 다르지만, 자기 자신을 더했을 때 얻게 되는 고유한 합의 개수는 $h=2$ 단계부터 모든 단계에서 정확히 같습니다. 논문은 크기가 3인 집합, 크기가 4인 집합에 대한 명시적인 구성을 제공하며, 임의의 크기 $k \ge 5$에 대한 일반적인 구성(크기가 4인 기본 집합에 연속된 정수 블록을 추가하는 방식)을 제시합니다. 이는 합집합의 크기 시퀀스를 세는 것만으로는 원래의 숫자 집합이 무엇인지 정확히 알 수 없음을 의미합니다. 왜냐하면 두 번째 단계부터 시작되는 크기 시퀀스의 "지문"이 해당 집합에 고유한 것이 아니기 때문입니다.

진동하는 춤

하지만 이야기는 더욱 흥미진진해집니다. 논문은 "진동(oscillation)"이라 불리는 현상을 탐구합니다. 두 명의 러너, 집합 A와 집합 B가 있다고 상상해 보세요. 때로는 A가 앞서고(더 큰 합집합을 가짐), 때로는 B가 앞섭니다. 논문은 다음과 같이 묻습니다: 우리가 원하는 만큼 번갈아 가며 선두를 바꿀 수 있을까?

저자는 특정 패턴에 대해 "예"라는 답을 내놓습니다. 집합의 숫자들을 신중하게 선택함으로써(구체적으로, 하나의 숫자가 멀리 떨어져 있는 연속된 숫자 블록처럼 보이는 집합들), 저자는 다음과 같은 시나리오를 설계할 수 있음을 보여줍니다:

• 초반 몇 단계 동안, 두 집합은 정확히 같은 수의 합을 만들어냅니다.
• 그 후, 특정 단계에서 집합 B가 갑자기 집합 A보다 더 많은 합을 만들어냅니다.
• 그리고 이 차이는 앞으로 나아갈수록 점점 더 커집니다.

논문은 임의의 단계 $h_1$에 대하여, $h_1$ 단계까지는 동일하지만 그 이후에는 집합 B가 앞서 나가며 영원히 앞서 나가는 두 집합을 찾을 수 있음을 증명합니다. 이는 첫 1마일 동안은 동률이었지만, 갑자기 속도를 내어 다시는 뒤를 돌아보지 않는 경주를 하는 두 러너와 같습니다.

형태를 바꾸는 경주

논문은 또한 세 개 이상의 집합이 참여하는 더 복잡한 게임을 다룹니다. 단순히 두 명의 러너를 비교하는 대신, $n$명의 러너가 있는 경주를 상상해 보세요. 저자는 "정규화(normalization)"라는 개념을 도입하는데, 이는 실제 속도와 상관없이 현재 누가 앞서고 있는지에 따라 러너들의 순위를 매기는 것과 같습니다. 만약 집합 A가 가장 작고, 집합 B가 중간이며, 집합 C가 가장 크다면, 그들의 "순위"는 (1, 2, 3)이 됩니다.

논문은 다음과 같은 매혹적인 질문을 던집니다: 우리가 미리 계획된 특정 순서에 따라 순위가 바뀌는 집합 그룹을 찾을 수 있을까? 예를 들어, 다음과 같은 세 집합을 찾을 수 있을까요?

1. 1단계에서는 순위가 A < B < C 입니다.
2. 2단계에서는 순위가 C < A < B로 바뀝니다.
3. 3단계에서는 다시 B < C < A로 바뀝니다.

논문은 이를 완전히 해결하지는 못했지만, 이 게임의 규칙을 설정해 둡니다. 그러나 2025년 1월에 추가된 최종 업데이트에서, 논문은 다른 수학자인 노아 크라비츠(Noah Kravitz)가 최근에 그렇다는 것을 증명했다고 언급합니다. 즉, 원하는 만큼 긴 시간 동안 원하는 특정 순위 시퀀스를 따르는 집합들을 만들 수 있으며, 마지막에는 영구적인 순위에 안착하게 할 수 있다는 것입니다.

여전히 남아있는 미지의 영역

이 논문은 여러 퍼즐을 풀었지만, 다른 이들을 위한 문을 활짝 열어두었습니다. 우리는 러너들이 복잡하고 교차하는 패턴(예를 들어 A가 이기고, 그다음 B가 이기고, 다시 A가 이기는 식)으로 순위를 바꾸게 만들 수 있을까요? 또한, 두 집합의 "최댓값"을 정확히 동일하게 유지하면서도 이 작업이 가능할까요? 이러한 열린 질문들은 다음 세대의 숫자 탐정들이 투입될 수 있도록 초대장을 보내고 있습니다.

요컨대, 이 논문은 숫자를 더하는 세계가 숨겨진 쌍둥이와 형태를 바꾸는 존재들로 가득 차 있음을 보여줍니다. 두 그룹의 숫자가 같은 속도로 성장한다고 해서 그것이 반드시 같은 그룹임을 의미하는 것은 아니며, 적절한 설정만 있다면 당신이 상상할 수 있는 거의 모든 패턴으로 그들을 춤추게 할 수 있습니다.