A sharp 5/8 bound for an Erd\H{o}s-Sós pairwise-sums problem

기술 요약: Erdős–Sós 쌍합 문제에 대한 날카로운 5/8 상한

문제 정의
본 논문은 쌍합(pairwise sums)에 관한 Erdős–Sós 추측의 특정 사례를 다룬다. $f_3(N)$을 $A \subseteq \{1, \dots, N\}$인 모든 부분집합 $A$에 대하여, 서로 다른 세 원소 $a, b, c \in A$가 존재하여 그들의 쌍합 $a+b, a+c, b+c$가 모두 $A$에 포함되도록 하는 최소 정수라고 하자. 이러한 집합을 "쌍합 삼중항 부재(pairwise-sum triple-free)" 집합이라 하며, 그러한 삼중항이 존재하지 않는 경우를 의미한다. 이 문제의 핵심은 $f_3(N)$의 점근적 거동을 결정하는 것이다.

이 연구 이전에는, $A = [\frac{N}{8}, \frac{N}{4}] \cup [\frac{N}{2}, N]$이라는 표준 구성을 통해 $f_3(N) \geq \frac{5}{8}N + O(1)$임을 보여주었다. 본 논문의 목표는 이와 일치하는 상한을 증명함으로써 Erdős Problem 865를 해결하고, 정확한 점근적 상수를 확립하는 것이다.

방법론
증명은 자기 완결적(self-contained)이며 조합론적 귀납법, 가법 정수론(additive number theory), 그리고 "폴딩(folding, 접기)" 기법의 결합에 의존한다. 방법론은 다음과 같은 주요 단계로 진행된다:

1. 접힌 가법 보조정리 (보조정리 2.1):
   저자들은 먼저 "접힌" 구간에 대한 보조정리를 확립한다. 서로 다른 한 쌍의 합이 $m$이나 $m$에 대한 나머지로서 $B$의 다른 원소가 되지 않는 집합 $B \subseteq \{1, \dots, m-1\}$에 대하여, 이 보조정리는 $B$의 크기를 충돌 집합 $C(B)$에 대한 상대적 크기로 제한한다. 구체적으로, $|B| - |C(B)| \leq \frac{m}{4} + 2$임을 증명한다. 이 증명은 반사 대칭($B \to -B$)과 $|B|$에 대한 귀납적 논증을 활용하며, 두 가장 작은 원소의 합이 $C(B)$에 속하는지 여부에 따른 경우를 분석한다.

2. 폴딩 보조정리 (보조정리 3.1):
   저자들은 피벗 원소 $h \in A$를 중심으로 하는 "폴딩" 연산을 도입한다. 집합 $A$를 $h$보다 작은 원소들($X$)과 $h+r$ 형태의 원소들($r < h$인 $Y$)로 분할함으로써, $A$의 크기를 교집합 $B_h = X \cap Y$의 구조와 연관시킨다. 이 보조정리는 만약 $A$가 삼중항 부재라면, $|X| + |Y|$의 합이 $\frac{5}{4}h - |E \setminus C(B_h)| + 1$로 제한됨을 보여준다. 여기서 $E$는 구간 $[1, h-1]$에서의 "간격(gaps)"을 나타낸다. 이 단계는 전역적 집합 크기를 구속하는 문제를 $h$에 대한 국소적 가법 성질을 분석하는 문제로 효과적으로 축소시킨다.

3. 귀납적 상한 (섹션 4):
   주 정리(main theorem)는 $N=2H$일 때 $H$에 대한 강한 귀납법을 통해 증명된다. 증명은 구간의 하반부에서 가장 큰 원소와 상반부에서 가장 작은 원소 사이의 간격에 따라 두 가지 경우로 나뉜다:

   • 경우 1 ($s \leq 4e$): 집합을 피벗 $h = q$($q$는 상반부의 가장 작은 원소)를 중심으로 접는다. 저자들은 하반부와 상반부 사이의 간격이 충분한 수의 "누락된" 원소($|E \setminus C(B_h)|$)를 강제함을 보여준다.
   • 경우 2 ($s > 4e$): 집합을 피벗 $h = p$($p$는 하반부의 가장 큰 원소)를 중심으로 접는다. 이 경우 큰 간격은 집합의 하단 부분이 희소함을 의미한다. 저자들은 하단 부분에 대해 귀납 가설을 적용하고, 이를 폴딩 보조정리와 결합하여 상한을 도출한다.

주요 기여 및 결과

• 날카로운 상한: 본 논문은 모든 $N$에 대하여, $|A| \geq \frac{5}{8}N + C$ (여기서 $C$는 절대 상수)를 만족하는 모든 부분집합 $A \subseteq [1, N]$가 쌍합 삼중항을 포함함을 증명한다.
• Erdős Problem 865 해결: 새로운 상한을 기존의 하한 구성과 결합함으로써, 본 논문은 $f_3(N) = \frac{5}{8}N + O(1)$임을 확립한다. 이는 상수 $5/8$이 최선임을 확인해 준다.
• 정형화: 저자들은 더 거친(coarser) 상한으로부터 날카로운 상한으로의 환원에 관한 이전의 조건부 버전이 Lean 4/Mathlib으로 정형화되었음을 언급한다. 이 정형화는 "sorries"(미결된 부분)나 추가된 공리 없이 수행되었으며, 환원 단계의 논리적 타당성을 검증한다.
• 정교화된 추측: 본 논문은 $N \pmod 8$에 따른 특정 $N$에 대한 정확한 최대 크기에 관해 Stijn Cambie가 제안한 더 정교한 추측 공식에 대해 언급한다. 다만, 주요 결과는 여전히 점근적 $5/8$ 상한이다.

의의
본 논문은 날카로운 $5/8$ 상한에 대한 자기 완결적 증명을 제공함으로써 Erdős Problem 865를 해결한다고 주장한다. 그 의의는 알려진 구성과 이론적 상한 사이의 간극을 메움으로써 이 특정 쌍합 문제에 대한 결론을 짓는 데 있다. 본 연구는 완전한 수학적 증명으로 제시되며, Lean을 통한 정형화된 환축을 통해 추가적인 검증되지 않은 가정에 의존하지 않고 조합론적 논증의 유효성을 보장하는 엄밀함을 더했다. 저자들은 증명이 자기 완결적이며 모든 암묵적 상수들이 절대 상수임을 명시적으로 밝히고 있다.