A Note on the Sum-Product Problem and the Convex Sumset Problem

당신에게 서로 다른 값이 적힌 구슬이 담긴 주머니처럼, 숫자들의 집합이 있다고 상상해 보십시오. 수학의 한 분야인 **가법 조합론(Additive Combinatorics)**에서 연구자들은 단순하지만 까다로운 질문을 던집니다: 이 숫자들을 함께 섞으면 어떤 일이 벌어지는가?

숫자를 섞는 데는 두 가지 주요 방법이 있습니다:

1. 덧셈: 두 수를 가져와서 더합니다 ($A + A$).
2. 곱셈: 두 수를 가져와서 곱합니다 ($A \times A$).

거대한 미스터리: 합-곱 문제 (The Sum-Product Problem)

오랫동안 수학자들은 두 명의 유명한 사상가, 에르되시(Erdős)와 세메레디(Szemerédi)가 제안한 퍼즐을 풀기 위해 노력해 왔습니다. 그들의 아이디어로 알려진 **합-곱 추측(Sum-Product Conjecture)**은 다음과 같습니다:

"덧셈과 곱셈 모두에서 '게으른(lazy)' 숫자 집합은 존재할 수 없다."

당신의 숫자들을 파티에 모인 사람들의 집단이라고 생각해 보십시오.

• 만약 집단이 매우 조직적(예: 숫자들이 정연하게 늘어선 형태)이라면, 더하기를 할 때 엄청난 규모의 새로운 합들이 만들어지지만, 곱하기를 할 때는 작고 반복적인 집단이 만들어질 수 있습니다.
• 만약 집단이 무질서(예: 무작위로 흩어진 형태)하다면, 곱하기를 할 때 엄청나 다양한 결과가 생길 수 있지만, 더하기를 할 때는 더 적은 수의 유일한 합들이 만들어질 수 있습니다.

이 추측은 당신이 숫자를 어떻게 배치하든, 덧셈이나 곱셈 중 적어도 하나의 활동은 규모가 폭발적으로 커져야 한다고 말합니다. 즉, 합의 크기도 작고 곱의 크기도 작은 상태를 동시에 유지할 수는 없습니다.

"성장"의 경주

수학자들은 이 "폭발"을 **지수(exponent)**를 사용하여 측정합니다.

• 만약 당신에게 $N$개의 숫자가 있다면, "완벽한" 폭발은 $N^2$입니다 (모든 쌍이 고유한 결과를 만들어내는 경우).
• 현재의 목표는 합 또는 곱의 크기가 적어도 $N^{2 - \text{아주 작은 수}}$ 이상임을 증명하는 것입니다.

오랫동안 알려진 최선의 보증은 그 크기가 적어도 $N^{1.33}$ (즉, $4/3$) 이상이라는 것이었습니다. 이는 "우리는 파티가 원래 크기의 제곱근보다 최소한 1.33배는 커질 것이라는 점은 알고 있지만, 우리는 그 성장이 전체 제곱에 훨씬 더 가까워지기를 원한다"라고 말하는 것과 같습니다.

이 논문이 하는 일: 아주 작은 밀기

아담 커스먼(Adam Cushman)의 논문은 이 미스터리 전체를 해결하지는 못하지만, 경계선을 아주 조금 더 밀어냅니다. 이것은 마치 수년간 특정 높이에 갇혀 있던 높이뛰기 선수와 같습니다. 커스먼은 세계 기록을 깨뜨리지는 못했지만, 바를 몇 밀리미터 차이로 넘었습니다.

새로운 기록:
커스먼은 어떤 숫자 집합에 대해서도 합 또는 곱의 크기가 적어도 다음 이상임을 증명합니다:
$$N^{1.333... + \text{아주 작은 분수}}$$
구체적으로 지수는 $4/3 + \frac{10}{4407}$입니다.

$\frac{10}{4407}$은 아주 작은 숫자처럼 보이지만, 순수 수학의 세계에서 이것은 중요한 진전입니다. 이는 "게으른" 집단이 우리가 이전에 생각했던 것만큼 결코 게으를 수 없음을 증명합니다.

특별한 경우: "볼록(Convex)" 파티

이 논문은 또한 **볼록 집합(Convex Sets)**이라 불리는 특수한 유형의 숫자 집합을 살펴봅니다.

• 비유: 당신의 숫자들이 계단의 디딤돌이라고 상상해 보십시오. 일반적인 집합에서는 계단이 불규칙할 수 있습니다. 하지만 볼록 집합에서는 위로 올라갈수록 계단이 점점 더 넓어집니다 (1번과 2번 디딤돌 사이의 간격보다 2번과 3번 사이의 간격이 더 큽니다).
• 이러한 엄격한 구조 때문에, 이 집합들은 다르게 행동합니다. 수학자들은 그들을 위한 별도의 규칙을 가지고 있습니다: 만약 당신이 볼록 집합을 가지고 있다면, 숫자들 사이의 차이(하나에서 다른 하나를 빼는 것)는 반드시 매우 커야 합니다.

커스먼은 이 "계단" 형태의 집합들에 대해서도 수학적 성장을 개선했습니다:

1. 합집합 (Adding): 그는 성장 보증을 $N^{46/29}$ (약 $1.586$)로 개선했습니다.
2. 차집합 (Subtracting): 그는 성장 보증을 $N^{1.600...}$ (구체적으로 $8/5 + \frac{1}{3440}$)로 개선했습니다.

그는 어떻게 해냈는가? (비법 소스)

이 논문은 집단 내에서 "인기 있는" 사람과 "부유한" 사람을 찾는 것으로 시각화할 수 있는 방법을 사용합니다.

1. "인기 있는" 차이: 저자는 숫자들 사이의 차이를 살펴보고, 어떤 차이가 가장 자주 발생하는지 식별합니다. 이것들이 "인기 있는" 차이들입니다.
2. "부유한" 요소들: 그런 다음 그는 가장 많은 인기 있는 차이들을 만들어내는 데 기여하는 원래 집합의 특정 숫자들을 찾아냅니다. 이들이 바로 "부유한" 요소들입니다.
3. 투영 (Projection): 그는 이 부유한 요소들이 있다면, 이들이 더 많은 고유한 합이나 차이를 만들어내도록 강제한다는 것을 보여주는 영리한 트릭(수학적 "투영")을 사용합니다.

이것은 다음과 같이 말하는 것과 같습니다: "만약 우리가 파티에서 가장 사교적인 사람들(부유한 요소들)을 찾고 그들이 누구와 대화하고 있는지(인기 있는 차이들)를 알 수 있다면, 우리는 이 사람들이 너무나 많은 새로운 연결을 만들어내기 때문에 파티가 우리가 생각했던 것보다 반드시 더 커질 수밖에 없다는 것을 증명할 수 있다."

요약

• 문제: 숫자 집합이 더할 때도 작고, 곱할 때도 작을 수 있을까? (수학은: 아니라고 답합니다.)
• 목표: 그들이 정확히 얼마나 커져야 하는지를 증명하는 것입니다.
• 결과: 커스먼은 그들이 이전의 최선이었던 추측보다 약간 더 커야 함을 증명했습니다.
• 방법: 집합 내에서 가장 "생산적인" 숫자들을 식별하고 그들이 어떻게 상호작용하는지 추적함으로써, 그는 결과물인 합과 곱의 집단이 이전의 생각만큼 작을 수 없음을 보여주었습니다.

이것은 순수 수학의 승리입니다. 이는 우리가 숫자가 어떻게 행동하는지에 대한 이해를 정교하게 다듬으며, 비록 그것이 당장 다리를 건설하거나 질병을 치료하는 데 직접적으로 쓰이지 않더라도, 수학적 우주의 지도를 한 걸음 더 정확하게 만드는 작업입니다.