Three-color van der Waerden numbers grow super-exponentially

기술 요약: 3색 반 데르 발덴 수(van der Waerden numbers)의 초지수적 성장

문제 정의
본 논문은 $w(k; r)$로 표기되는 반 데르 발덴 수의 성장률을 다룬다. 이 수는 모든 $r$-채색(r-coloring)이 된 집합 $\{1, 2, \dots, N\}$ 내에 반드시 길이가 $k$인 단색 등차수열(monochromatic arithmetic progression)을 포함하게 하는 최소 정수 $N$으로 정의된다. 이러한 수들의 존재는 반 데르 발덴의 정리에 의해 보장되지만, 이들의 정확한 점근적 성장률은 여전히 근본적인 미해결 문제로 남아 있다.

역사적으로 $w(k; r)$의 성장은 강렬한 추측의 대상이었다. 고정된 $r$에 대하여, 에르되시(Erdős)는 $w(k; 2)$가 초지수적으로 성장할 것($\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$)이라고 추측했다. 반대로, 다른 추측들은 선형 지수적 성장을, 구체적으로는 $\lim_{k \to \infty} w(k; r)^{1/k} = r$을 제안했다. 본 연구 이전까지 $w(k; r)$에 대한 알려진 최선의 하한값은 주로 로바츠 국소 르마(Lovász Local Lemma)나 특정 대수적 구조로부터 유도되었으며, $w(k; r) \geq r^{k-1}/(4k)$ 형태나, 고정된 $r \geq 5$에 대해 $(3r/3)^{(1-o(1))k}$ 형태의 하한값을 나타냈다. 저자들은 헌터(Hunter) [20]의 선행 연구가 $r \geq 5$인 경우에 대해 선형 지수 추측을 반박했으나, $r=3$인 경우(및 작은 고정된 $r$에 대한 일반적인 거동)는 여전히 해결되지 않은 상태였다고 언급한다.

방법론
저자들은 $w(k; r)$의 하한을 설정하기 위해 새로운 확률적 구성을 개발한다. 이 방법론은 세 가지 주요 구성 요소에 의존한다:

1. 순환 군(Cyclic Groups)에서의 조밀한 무진행 집합(Progression-Free Sets):
   저자들은 $k$-항 등차수열($k$-AP)을 포함하지 않는 순환 군 $\mathbb{Z}_N$의 매우 조밀한 부분집합을 구성한다. 이들은 에르되시-투란(Erdős-Turán) 구성을 확장하여 순환 군에 적응시킨 방식(기수 $p$에서 $p-1$과 같은 숫자를 갖지 않는 정수 집합)을 활용한다. 결정적으로, 저자들은 (밀도 $\leq \epsilon$이면서) 순환 군 내의 모든 $k$-AP와 상수 비율의 원소를 교차하는 "히팅 셋(hitting sets)"(보조정리 2.8)이 존재함을 증명한다. 이는 소수들의 집합에 대한 합동류(congruence classes)를 무작위로 선택함으로써 달성된다.

2. 로바츠 국소 르마(LLL)의 결과:
   본 논문은 대칭 버전의 로바츠 국소 르마를 사용하여, 어떤 색상 클래스도 $k$-AP의 "큰" 비율을 차지하지 않는 채색의 존재를 입증한다. 구체적으로, 보조정리 3.3은 작은 소인수가 없는 차수 $N$을 가진 군에 대해, 어떤 $k$-AP도 단색이거나 거의 단색이 되지 않도록 정점들에 색상 부분집합을 할당할 수 있음을 확립한다.

3. 무작위 이동 곱 구성(Random Shifted Product Constructions):
   핵심적인 기술적 혁신은 정교한 "무작위 이동 곱" 구성(보조정리 4.2 및 4.3)이다. 표준적인 곱 채색(product colorings)이 색상의 수를 곱하는 것과 달리, 이 방법은 색상의 수를 고정하거나(또는 통제된 방식으로 증가시키며) 더 작은 군의 채색들을 더 큰 군의 채색으로 결합할 수 있게 한다.

• 메커니즘: $H_1$의 채색 $c_1$과 $H_2$의 채색 $c_2$가 주어졌을 때, 이 구성은 $H_2$로의 투영에 대한 파이버(fibers)를 독립적으로 이동시키고 $H_1$의 기저 원소의 색상에 따라 색상을 치환함으로써 $H_1 \times H_2$ 상의 채색을 정의한다.
• 반복 과정: 저자들은 이 구성을 반복한다. 각 단계에서 저자들은 군 $\mathbb{Z}_{n_{j-1}}$의 채색과 소수 차수의 순환 군 $\mathbb{Z}_{q_j}$의 채색을 결합한다. 이 구성은 군의 크기를 $k$에 대해 지수적으로 증가시키는 동시에, "좋은" 색상 클래스의 밀도 매개변수에서 "이중 지수적" 손실을 발생시킨다. 이 매개변수들을 신중하게 균형 잡음으로써, 이 과정은 약 $(\log^* k)/2$번 반복될 수 있다.

주요 기여 및 결과

• 3색에 대한 초지수적 성장:
  주요 결과(정리 1)는 충분히 큰 $k$에 대하여 3색 반 데르 발덴 수가 다음을 만족함을 증명한다:
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  이는 $w(k; 3)$이 $k$의 임의의 지수 함수보다 빠르게 성장함을 입증하며, 이를 통해 $r \geq 3$인 경우 $\lim_{k \to \infty} w(k; r)^{1/k} = r$이라는 추측을 반박한다.

• 많은 색상에 대한 하한:
  정리 2는 색상의 수 $r$이 $k$에 비해 매우 큰 경우(구체적으로 $r \geq (\log k)^{3/\epsilon}$)의 하한을 제공한다:
  $$w(k, r) \geq r^{(1-\epsilon)k \log k}$$
  이는 "많은 색상" 영역에서 기존의 하한을 개선한 것이다.

• 에르되시-그레이엄 문제의 해결:
  저자들은 모든 채색이 $[N]$ 내에서 단색 또는 무지개(rainbow) $k$-AP를 포함하게 하는 최소 $N$인 정형 반 데르 발덴 수(canonical van der Waerden number) $H(k)$를 다룬다. 에르되시와 그레이엄은 $H(k)^{1/k}/k \to \infty$인지 여부를 추측했다. $w(k, k-1)$에 대한 개선된 하한을 사용하여, 저자들은 정리 3을 통해 다음을 증명한다:
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  이는 $H(k)$가 초지수적으로 성장함을 확인하며, 에르되시와 그레이엄이 제기한 미해결 문제를 해결한다.

의의
본 논문은 3개 이상의 색상에 대한 반 데르 발덴 수의 성장이 초지수적임을 주장하며, 이는 이러한 조합론적 수들에 대한 이해를 근본적으로 변화시키는 결과이다. 그 의의는 다음과 같다:

1. 선형 지수 추측의 반박: $r \geq 3$인 경우 $w(k; r)$이 $r^k$처럼 행동하지 않음을 확정적으로 보여준다.
2. 방법론적 진보: "무작위 이동 곱" 구성의 도입은 고정된 수의 색상을 유지하면서 확률적 논증을 반복할 수 있게 하며, 이는 저자들이 $r \geq 5$를 위해 사용했던 이전 버전들보다 더 효율적이라고 언급한 기술이다.
3. 정형 램지 이론(Canonical Ramsey Theory): 저자들의 결과는 무지개 진행(rainbow progressions)을 허용하더라도 $H(k)$가 이전에 알려진 하한보다 훨씬 더 크게 성장함을 보여줌으로써, 에르되시-그레이엄 문제에 대한 강력한 해결책을 제공한다.

저자들은 자신들의 기술이 일반적이지만, 본 연구의 구체적인 적용은 이러한 하한을 설정하는 데 집중되어 있다고 언급한다. 그들은 이러한 구성들이 다른 산술 램지 수(arithmetic Ramsey numbers)의 새로운 하한을 얻는 데 적용될 수 있음을 시사하며, 이는 향후 동반 논문에서 탐구할 주제라고 밝힌다. 본 논문은 정확한 성장률이나 상한을 결정한다고 주장하는 것이 아니라, 기존보다 훨씬 강력한 하한을 설정하는 데 목적이 있다.