A $(\log n)^{1/4}$ Bound for the Komlós Problem

기술 요약: Komlós 문제에 대한 $(\log n)^{1/4}$ 상한

문제 정의
본 논문은 모든 실수 행렬 $A \in \mathbb{R}^{m \times n}$의 열의 유클리드 노름이 1 이하일 때, 조합적 불일치(combinatorial discrepancy) $\text{disc}(A) = \min_{\sigma \in \{-1,1\}^n} \|A\sigma\|_\infty$가 절대 상수(absolute constant)로 유계된다는 Komlós 추측을 다룬다. Banaszczyk가 $O(\sqrt{\log n})$ 상한을 확립한 가운데, 본 연구의 목표는 이를 $n$에 독립적인 상수로 개선하는 것이다. 최근의 연구인 Bansal과 Jiang [BJ25, BJ26]은 아핀 스펙트럼 독립성(affine spectral independence) 프레임워크를 도입하여 $O((\log n)^{1/4}(\log \log n)^{7/4})$ 상한을 달성하였다. 본 논문은 이 $(\log \log n)^{7/4}$ 인자를 제거하는 것을 목표로 한다.

방법론 및 프레임워크
본 구성은 Bansal-Jiang 프레임워크, 특히 그들의 아핀 스펙트럼 독립성 정리(Theorem A.4)와 준정부호 계획법(SDP)을 통한 디커플링(decoupling) 개념을 활용한다. 핵심 방법론은 분수적 채색(fractional coloring) $b \in [-1, 1]^n$을 부호화(signing) $\sigma$로 진화시키는 유한 궤적(finite trajectory) 구성이다.

주요 기술적 구성 요소는 다음과 같다:

1. 연쇄적 제한 및 크기 클래스(Successive Restrictions and Size Classes): 알고리즘은 현재 "살아있는"(unfrozen) 좌표에서의 제곱 질량(squared mass)을 기준으로 행들을 "크기 클래스"로 분해하여 처리한다. 행들은 큰 계수를 나머지 부분과 분리하기 위해 "껍질을 벗겨지며"(peeled), 이를 통해 각 클래스 내의 남은 계수들이 유계되도록 보장한다.
2. 정규화된 불일치 및 드리프트(Regularized Discrepancy and Drift): 각 부호화된 제한(signed restriction)에 대해, 정규화된 불일치 함수 $Z_c^\varepsilon(x)$가 정의된다. 이 함수는 음의 드리프트(negative drift)를 유도하기 위해 이차 에너지 항을 포함한다. 구성 과정에서 만약 특정 제한의 불일치가 임계값을 초과하면, 이후 단계에서 그 움직이는 그래디언트(moving gradient)가 차단되어 추가적인 성장을 방지하도록 한다.
3. 역사적 지수 합(Historical Exponential Sums): "위험한" 제한들(임계값 근처에 있는 것들)의 수를 제어하기 위해, 본 논문은 역사적 지수 합을 도입한다. 이 합은 제한들이 은퇴(freeze)한 후에도 그 이력을 추적한다. 포텐셜 함수 $\Psi_t$는 모든 크기 클래스와 열에 걸쳐 이들의 가중 지수 합을 집계하여 유지된다.
4. 유한 단계 분석(Finite-Step Analysis): 극한 프로세스에 의존할 수 있는 이전의 접근 방식들과 달리, 본 구성은 유한 메쉬(finite mesh) $\gamma$를 사용한다. 저자는 테일러 전개를 4차 항까지 사용하여 정밀한 1단계 지수 상한(Theorem 5.3)을 도출한다. 이 상한은 다음 사항들에 의존한다:
   • 아핀 스펙트럼 독립성: 부호화된 응답(signed responses)의 합에 대한 공분산을 제어한다.
   • 음의 곡률(Negative Curvature): 큐브 경계 근처의 "버퍼"에 의해 제공되며, 이는 포텐셜의 2차 미분값이 음수가 되도록 보장한다.
   • 4차 나머지 항(Fourth-Order Remainder): 단일 단계에서 기대값이 증가하지 않도록 유계되는 것을 보장하기 위해 균등하게 유계된다.

주요 기여

• $(\log \log n)$ 인자 제거: Bansal-Jiang 상한에 존재하던 $(\log \log n)^{7/4}$ 인자를 제거한 것이 주요 기여이며, 결과적으로 $O((\log n)^{1/4})$ 상한을 달성하였다.
• 정확한 임계값 합 인증(Exact Threshold Sum Certificate): 크기 클래스에 걸친 임계값의 합에 대해 명시적이고 정확한 수치적 인증을 제공한다. 이를 통해 점근적인 값이 아닌 정밀한 상수를 최종 상한에 적용할 수 있다.
• 규정된 깊이의 부분 채색(Prescribed-Depth Partial Coloring): 정리 1.2는 임의의 분수적 지점 $b$에서 시작하여 규정된 "깊이" $R$에서 멈출 수 있는 부분 채색 결과를 확립한다. 이는 남은 분수적 좌표의 수가 최대 $\max\{\lceil q e^{-R} \rceil - 1, 8\}$로 감소함을 보장한다 (여기서 $q$는 초기 분수적 좌표의 수).
• Lean을 통한 형식화: 유한 궤적, 정확한 임계값 합, 최종 라운딩을 포함한 전체 증명이 Lean 정리 증명기(theorem prover) 내에서 형식화되었다. 외부 가정은 오직 Bansal-Jiang의 Theorem A.4뿐이다.

주요 결과
본 논문은 다음과 같은 명시적 상한(Theorem 1.1)을 증명한다:
$$\text{disc}(A) \le 2395 \left(1 + \log_+ \frac{n}{9}\right)^{1/4} + 2\sqrt{2}$$
여기서 $\log_+ t = \max\{0, \log t\}$이다.

또한, 추론 1.3은 $q$개의 분수적 좌표를 가진 임의의 시작점 $b$에 대하여, 기존 부호를 유지하는 부호화 $\sigma$가 존재하여 다음을 만족함을 보여준다:
$$\|A(\sigma - b)\|_\infty \le 2395 \left(1 + \log_+ \frac{q}{9}\right)^{1/4} + 2\sqrt{2}$$
$q \le 8$인 경우, 직접적인 유클리드 라운딩을 통해 상한은 $\sqrt{q}$로 개선된다.

의의 및 주장
본 논문은 $(\log \log n)$의 폴리로그(polylogarithmic) 인자 없이 $O((\log n)^{1/4})$ 속도를 달성하는 최초의 Komlós 문제 상한을 제공한다고 주장한다. 4제곱근 지수는 살아있는 집합의 차원 감소와 공분산 예산의 4제곱 사이의 균형을 맞추는 과정에서 발생한다.

저자는 본 구성이 "유한"하고 "정확"하며, 극한 논증을 피한다는 점을 강조한다. 유한 메쉬와 명시적 유리 상수(예: 계수 2395)의 사용은 컴퓨터로 검증된 엄밀한 증명을 가능하게 한다. 이 연구는 부분 및 전체 채색 정리를 형식화함으로써, 원래의 스펙트럼 독립성 논증의 구조적 무결성을 유지하면서도 더 타이트하고 명시적인 상수를 얻기 위해 Bansal-Jiang 프레임워크를 어떻게 정교화할 수 있는지 보여준다. 본 논문은 Komlós 추 conjecture를 해결한다고 주장하는 것이 아니라($\log n$에 독립적인 상수를 요구함), 로그 의존성을 단일 루트로 고립시킴으로써 그 방향으로 중요한 진전을 이루었다고 밝히고 있다.