Randomstrasse101: Open Problems of 2025

제공된 논문은 ETH 취리히 수학부의 연구 그룹 (Afonso S. Bandeira 등) 이 운영하는 블로그 'Randomstrasse101'에 2025 년에 게시된 16 개의 오픈 문제 중 7 개 (Entry 8~14) 를 발췌하여 정리한 문서입니다. 이 문서는 확률론, 계산 이론, 조합론, 통계학 및 관련 분야의 미해결 문제들을 다루며, 각 문제의 배경, 현재까지의 연구 성과, 그리고 제기된 새로운 추측 (Conjecture) 을 기술하고 있습니다.

요청하신 대로 각 섹션별 문제, 방법론, 주요 기여, 결과 및 의의를 포함한 상세한 기술적 요약은 다음과 같습니다.

---

논문 개요: Randomstrasse101 의 2025 년 오픈 문제들

이 문서는 수학적 난제들에 대한 학술적 참고를 용이하게 하기 위해 작성된 것으로, 주로 텐서 농도 부등식, 랜덤 그래프의 Lovász 수, 위상 재구성 (Phase Retrieval), Mutually Unbiased Bases(MUB), Paley 그래프의 클릭 수, KLS 추측, 그리고 그래프 행렬의 경계 등 7 가지 핵심 주제를 다룹니다.

---

1. 텐서 농도 부등식 (Tensor Concentration Inequalities)

• 문제: 대칭 결정론적 텐서 $T_1, \dots, T_n$과 i.i.d. 표준 가우스 변수 $g_i$에 대해, $\ell_p$ 노름 하에서의 텐서 합 $\sum g_i T_i$의 기대값 상한을 구하는 문제입니다. 이는 텐서 주성분 분석 (PCA), Banach 공간 기하학, 가우스 과정 이론 등과 밀접하게 연관되어 있습니다.
• 방법론 및 배경:
  • $r=p=2$ (대칭 행렬) 인 경우, Ahlswede-Winter 부등식과 비가환 Khintchine 부등식을 통해 로그 인자 ($\log d$) 와 함께 $\sqrt{n}$ 스케일의 농도 부등식이 알려져 있습니다.
  • 일반적인 $r, p \ge 2$의 경우, 스펙트럼 노름을 트레이스로 근사하는 고전적인 기법이 적용되지 않으며, injective 노름 근사는 NP-hard 문제입니다.
  • Dudley's entropy integral를 사용하여 거리 함수 $D$에 대한 덮개 수 (covering number) $N(B_p^d, D, \varepsilon)$를 추정하는 접근법이 사용됩니다.
• 주요 기여 및 결과:
  • Conjecture 16 (텐서의 Type-2 상수): $p \ge 2$일 때, 기대값이 $\tilde{O}_{r,p}(d^{1/2 - 1/p} \sqrt{\sum ||T_i||_{I_p}^2})$로 상한이 잡힐 것이라고 추측합니다.
  • $p \ge 2r$인 경우에는 덮개 수 추정치를 통해 문제가 해결되었으나, $p < 2r$인 경우 (응용에 중요한 영역) 는 부피 장벽 (volumetric barrier) 으로 인해 증명되지 않았습니다.
  • 최근 연구 (Aden-Ali, Boedihardjo 등) 에서 로그 인자를 제거하거나 독립 성분 텐서에 대해 정밀한 경계를 얻는 진전이 있었으나, 일반적인 경우의 crude bound 증명에는 여전히 어려움이 있습니다.
• 의의: 고차원 텐서 데이터의 통계적 성질을 이해하고, 텐서 PCA 및 신호 처리 알고리즘의 이론적 한계를 규명하는 데 필수적입니다.

---

2. 랜덤 순환 그래프의 Lovász 수 (The Lovász number of random circulant graphs)

• 문제: Erdős-Rényi 랜덤 그래프 $G(n, 1/2)$와 Paley 그래프 사이의 중간 단계인 '랜덤 조밀 순환 그래프 (random dense circulant graphs)'의 Lovász 수 $\vartheta(G)$의 점근적 거동을 규명하는 문제입니다.
• 방법론:
  • 순환 그래프의 구조적 특성 (Cayley graph over $\mathbb{Z}_n$) 을 이용하여 Lovász 수를 선형 계획법 (LP) 으로 변환합니다.
  • 이산 푸리에 변환 (DFT) 행렬을 사용하여 '시간 영역 (time domain)'과 '주파수 영역 (frequency domain)' 사이의 LP 쌍대성을 활용합니다.
  • 부분 샘플링된 DFT 행렬의 제한 등거리성 (RIP) 성질을 분석합니다.
• 주요 기여 및 결과:
  • Conjecture 17 & 18: $G(n, 1/2)$와 랜덤 순환 그래프 모두에서 $E[\vartheta(G)] = (1+o(1))\sqrt{n}$일 것이라고 추측합니다.
  • 기존 연구 [BBD+25] 를 통해 하한과 상한 $O(\sqrt{n} \log \log n)$을 제시했으나, 정확한 $\sqrt{n}$ 스케일 증명은 미해결 상태입니다.
• 의의: Shannon 용량 (Shannon capacity) 의 정확한 값 계산 및 조합론적 최적화 문제의 근사 알고리즘 성능 분석에 중요한 역할을 합니다.

---

3. 위상 재구성의 단사성과 안정성 (Injectivity and Stability of Phase Retrieval)

• 문제: 복소수 또는 실수 공간에서 $|Ax|$(측정값의 크기) 만 주어졌을 때 벡터$x$를 복원하는 위상 재구성 문제에서, 측정 행렬$A$가 단사적 (injective) 인지 여부와 복원 과정의 안정성 (stability) 을 결정하는 조건을 규명합니다.
• 방법론:
  • 단사성: $N \ge 4M-4$ (복소수) 또는 $N \ge 2M-1$ (실수) 측정값이 필요하다는 기존 결과를 바탕으로, $N=4M-5$인 경우의 단사성 확률을 분석합니다.
  • 안정성: Balan-Wang 가설을 기반으로, 행렬 $A$의 부분 행렬들이 $\mathbb{R}^M$을 스패닝할 때의 조건수 (condition number) 와 관련된 $\omega(A)$ 값을 분석합니다.
• 주요 기여 및 결과:
  • Conjecture 19: $N=4M-5$인 경우, 임의의 $M$에 대해 단사성 확률 $p_M < 1$이며, $M \to \infty$일 때 $p_M \to 0$일 것이라고 추측합니다.
  • Conjecture 20 & Open Problem 21: $\omega(A)$의 상한을 행렬 노름과 연결하는 보편적 상수 $\beta$의 존재를 추측하고, 가우스 행렬에 대한 $\omega(A)$의 정확한 값을 구하는 문제를 제기합니다.
• 의의: X-선 회절, 전자 현미경 등 위상 정보가 손실된 신호 처리 분야에서 안정적인 복원 알고리즘 설계의 이론적 토대를 제공합니다.

---

4. Mutually Unbiased Bases (MUB), ETF 및 Zauner 추측

• 문제: 양자 물리학 및 유한 프레임 이론에서 중요한 '상호 무관 기저 (MUB)'와 '등각 조밀 프레임 (ETF)'의 존재성을 다룹니다.
• 방법론:
  • MUB: $d$차원 공간에서 최대 $d+1$개의 MUB가 존재할 수 있으며, $d$가 소수 거듭제곱일 때만 존재가 증명되었습니다. $d=6$인 경우의 존재 여부가 핵심 난제입니다.
  • ETF: $n=d^2$인 ETF (SIC-POVM) 의 존재성을 다룹니다.
  • Sum-of-Squares (SoS) 증명: MUB(6) < 7 임을 증명하기 위해 SoS 계층 구조 (특히 4 차) 를 활용하는 접근법을 제안합니다.
• 주요 기여 및 결과:
  • Conjecture 22: $MUB(6) < 7$일 것이라고 추측합니다 (현재 알려진 하한은 3).
  • Open Problem 23: 7 개의 MUB가 존재하지 않음을 증명하는 SoS 4 차 증명의 존재 여부를 묻습니다.
  • Conjecture 24 (Zauner's Conjecture): 모든 차원 $d$에 대해 $n=d^2$인 ETF 가 존재합니다. 최근 정수론적 추측 (Stark Conjectures) 을 가정하면 부분적으로 증명되었으나, 무조건적 증명은 미해결입니다.
• 의의: 양자 상태 추정 (Quantum State Tomography) 및 양자 암호 통신의 핵심 요소인 SIC-POVM 의 존재성을 수학적으로 확립하는 데 기여합니다.

---

5. Paley 그래프의 클릭 수 (On the clique number of the Paley Graph)

• 문제: 소수 $p \equiv 1 \pmod 4$에 대한 Paley 그래프 $G_p$의 클릭 수 (clique number) $\omega(G_p)$가 다항 로그 ($O(\text{polylog}(p))$) 스케일인지, 아니면 $\sqrt{p}$ 스케일인지 규명하는 문제입니다.
• 방법론:
  • Lovász $\vartheta$ 함수: $\omega(G_p) \le \vartheta(G_p) \le \sqrt{p}$라는 기존 상한을 개선하기 위해 국소화 (localization) 기법과 고차 Sum-of-Squares (SoS) 완화 (relaxation) 를 사용합니다.
  • 국소화: 1-국소화 ($G_{p,1}$) 및 2-국소화 ($G_{p,2}$) 그래프의 $\vartheta$ 값을 분석하여 상한을 점진적으로 낮추는 접근을 취합니다.
• 주요 기여 및 결과:
  • Conjecture 25: $\omega(G_p) = O(\text{polylog}(p))$일 것이라고 추측합니다.
  • Conjecture 26 & 27: 국소화 그래프들의 $\vartheta$ 값이 $\sqrt{p}$보다 작아지며, 2-국소화에서는 $2/3 \sqrt{p}$ 이하일 것이라고 추측합니다.
  • Conjecture 28: 4 차 SoS 완화는 $\sqrt{p}$를 넘어 $O(p^{1/2-\varepsilon})$의 상한을 줄 수 있을 것이라고 추측합니다.
  • Conjecture 29: Paley ETF 가 '제곱근 병목 (square-root bottleneck)'을 넘어서는 제한 등거리성 (RIP) 을 만족할 것이라고 추측합니다.
• 의의: 의사난수 그래프 (pseudorandom graphs) 의 구조적 특성을 이해하고, 희소 복원 (sparse recovery) 및 암호학에서의 난수 생성기 설계에 중요한 통찰을 제공합니다.

---

6. KLS 추측과 그 함의 (The KLS Conjecture and Implications)

• 문제: 로그 볼록 (log-concave) 확률 분포에 대한 등주성 (isoperimetric) 상수 $\psi_\mu$가 차원에 무관한 하한을 가지는지 (KLS 추측) 를 다룹니다.
• 방법론:
  • 확산 국소화 (Stochastic Localization): Eldan 가 제안한 확률 과정을 통해 측도를 가우스 분포의 혼합으로 분해하고, 시간 $T$에 따른 등주성 상수의 변화를 분석합니다.
  • Thin Shell Conjecture 및 Slicing Problem: KLS 추측이 Thin Shell 추측과 Bourgain 의 Slicing 문제와 어떻게 연결되는지 설명합니다.
• 주요 기여 및 결과:
  • Conjecture 30: 모든 로그 볼록 측도에 대해 등주성 상수가 가우스 경우와 유사하게 하한을 가진다는 KLS 추측을 재확인합니다.
  • 최신 결과: Klartag 와 Lehec (2025) 에 의해 Thin Shell 추측이 증명되었고, 이는 현재까지 알려진 KLS 추측의 최상한 하한 ($\psi_n \ge C \log(n)^{-1/2}$) 을 유도합니다.
  • 함의: 볼록체에서의 볼 walk (ball walk) 알고리즘의 혼합 시간 (mixing time) 이 $\tilde{O}(n^2)$임을 보장하며, 고차원 볼록 기하학의 여러 난제 해결에 핵심적입니다.
• 의의: 고차원 확률론, 최적화 알고리즘, 그리고 볼록 기하학의 기본 구조를 이해하는 데 있어 가장 중요한 추측 중 하나입니다.

---

7. 그래프 행렬의 정밀한 경계 (Sharp Bounds for Graph Matrices)

• 문제: Sum-of-Squares (SoS) 계층 구조 하에서 그래프 행렬 (Graph Matrices) 의 스펙트럼 노름을 정밀하게 추정하는 문제입니다. 이는 SoS 알고리즘의 하한 증명에 필수적입니다.
• 방법론:
  • 그래프 행렬: 랜덤 입력 (Rademacher 변수) 에 의존하는 행렬을 '모양 (shape)' $\alpha$에 따라 정의합니다.
  • 행렬 혼돈 (Matrix Chaos): 그래프 행렬을 고차 다항식 형태의 행렬 혼돈으로 간주하고, 비가환 Khintchine 부등식과 자유 확률론 (free probability) 기법을 반복 적용합니다.
  • Pseudo-calibration: SoS 하한 증명을 위한 가상 기대값 (pseudo-expectation) 을 구성하는 과정에서 발생하는 행렬의 양의 정부호성 (PSD) 을 검증합니다.
• 주요 기여 및 결과:
  • Conjecture 31 (정밀한 그래프 행렬 경계): 그래프 행렬 $M_\alpha$의 기대 노름이 $E\|M_\alpha\| = \Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$ 형태일 것이라고 추측합니다.
  • 기존 연구에서는 불필요한 다항 로그 인자가 포함되었으나, 정밀한 형태 함수 $f, g$를 규명하여 SoS 하한 증명의 정밀도를 높이는 것을 목표로 합니다.
• 의의: 계산 복잡도 이론에서 SoS 알고리즘의 한계를 정확히 규명하고, 랜덤 행렬 이론과 최적화 이론의 교차점에서 새로운 수학적 도구를 개발하는 데 기여합니다.

---

종합적 의의 및 결론

이 논문은 현대 수학 및 이론 컴퓨터 과학의 최전선에 있는 확률론적 구조와 최적화 문제의 핵심 난제들을 체계적으로 정리했습니다.

1. 이론적 연결성: 텐서 농도, 그래프 이론, 양자 정보, 볼록 기하학 등 서로 다른 분야가 어떻게 서로 다른 수학적 도구 (SoS, 가우스 과정, 등주성 부등식) 를 통해 연결되는지를 보여줍니다.
2. 방법론적 발전: 기존의 로그 인자를 제거하거나 정밀한 상한을 찾는 시도 (예: KLS 추측의 최근 해결, 그래프 행렬의 정밀 경계) 를 통해 수학적 도구의 정교화가 진행 중임을 시사합니다.
3. 미래 연구 방향: 제시된 7 가지 추측과 오픈 문제는 향후 수년 간 확률론, 조합론, 계산 이론 분야의 주요 연구 방향을 제시하며, 특히 SoS 계층 구조의 한계 규명과 고차원 기하학의 구조 이해에 중요한 이정표가 될 것입니다.

이 문서는 단순한 문제 나열을 넘어, 각 문제의 배경, 현재까지의 진전 상태, 그리고 해결을 위한 구체적인 전략 (예: SoS 완화, 스토캐스틱 국소화, 행렬 혼돈 이론) 을 상세히 기술하여 연구자들에게 귀중한 로드맵을 제공합니다.