Discrete trace formulas and holomorphic functional calculus for the adjacency matrix of regular graphs

이 논문은 특정 타원체 상의 정칙 함수 계산(holomorphic functional calculus)을 활용하여 정규 그래프의 인접 행렬을 비역추적 행렬(non-backtracking matrices)의 관점에서 전개함으로써, 스펙트럼 이론과 그래프 조합론을 연결하는 이산 트레이스 공식을 유도하고, 경로 수 세기, 이하라-바스 공식(Ihara-Bass formula), 그리고 그래프 기반 열 및 슈뢰딩거 방정식과 같은 문제들에 대한 새로운 증명을 제공하는 통합 프레임워크를 소개한다.

핵심

모든 교차로(정점)가 일방통행 도로(간선)로 연결된 도시를 상상해 보십시오. 수학에서는 이를 **그래프(graph)**라고 부릅니다. 이제 이 도시의 모든 교차로에서 나가는 도로의 수가 정확히 동일하다고 상상해 봅시다. 이것이 바로 **정규 그래프(regular graph)**입니다.

이 논문의 저자들인 공(Gong), 리(Li), 유(Liu)는 이 도시들을 이해하기 위한 새로운 "만능 번역기"를 구축했습니다. 그들의 목표는 도시를 바라보는 두 가지 매우 다른 관점을 연결하는 것입니다:

1. 스펙트럼 관점 (The Spectral View): 도시의 "진동" 또는 주파수(수학적으로 인접 행렬의 고유값)라는 렌즈를 통해 도시를 바라보는 것.
2. 걷기 관점 (The Walking View): 사람들이 길을 따라 갈 수 있는 실제 경로의 수를 세는 것.

다음은 그들의 발견을 일상적인 비유를 사용하여 쉽게 풀어낸 내용입니다.

1. 문제점: "백트래킹(Backtracking)"의 혼란

만약 여러분이 "교차로 A에서 교차로 B까지 10걸음 만에 갈 수 있는 방법이 몇 가지인가요?"라고 묻는다면, 그 답은 보통 거대하고 복잡한 숫자가 될 것입니다. 왜 그럴까요? 대부분의 그 경로들이 **백트래킹(되돌아오기)**을 포함하고 있기 때문입니다.

• 백트래킹: 길을 따라 걷다가 실수를 깨닫고, 방금 왔던 길로 즉시 되돌아가는 것을 말합니다.
• 혼란: 거대한 도시에서 이러한 "앞으로 갔다가 다시 뒤로 오는" 경로의 수는 압도적이고 복잡합니다. 이는 마치 안개 속을 정처 없이 떠도는 사람의 발걸음을 하나하나 세려고 노력하는 것과 같습니다.

저자들은 **비백트래킹 걷기(Non-Backtracking Walks)**에 집중합니다. 이 경로는 결코 즉시 되돌아오지 않는 경로입니다. 앞으로 나아가고, 왼쪽으로 돌고, 오른쪽으로 돌지만, 바로 다음 단계에서 유턴(U-turn)을 하지는 않습니다.

• 비유: 이는 새로운 풍경을 보기 위해 결심한 나머지, 방금 지나온 길을 즉시 되돌아가지 않기로 한 관광객의 경로와 같습니다. 그들의 경로는 훨씬 "깔끔하고" 추적하기 쉽습니다.

2. 해결책: 특별한 "번역기" (홀로모픽 함수 계산법, Holomorphic Functional Calculus)

저자들은 **홀로모픽 함수 계산법(holomorphic functional calculus)**이라는 정교한 수학적 도구를 사용합니다.

• 은유: 여러분에게 데이터(그래프의 인접 행렬과 같은 복잡한 기계)를 처리하는 복잡한 기계가 있다고 상상해 보십시오. 보통, 특정 입력(예: 열 방정식이나 파동)에 대해 이 기계가 어떻게 작동하는지 이해하려면 어려운 퍼즐을 풀어야 합니다.
• 혁신: 저자들은 수학적 풍경 속의 특정한 **타원(ellipse)**을 사용하여, 어떤 매끄럽고 잘 정의된 함수(파동이나 열 패턴 등)라도 기계에 직접 "삽입"할 수 있는 방법을 찾아냈습니다.
• 결과: 그들의 방식은 답을 풀기 어려운 방정식으로 만드는 대신, 답을 **비백트래킹 행렬(Non-Backtracking Matrices)**의 깔끔한 무한 급수로 확장해 줍니다.

이렇게 생각해 보십시오. 혼란스러운 군중의 움직임을 파악하기 위해 모든 사람의 불규칙한 움직임을 추적하는 대신, 오직 직선으로 걷는 사람들만을 추적하면 군중 전체의 행동을 완벽하게 재구성할 수 있다는 사실을 깨달은 것과 같습니다.

3. 핵심 발견: 트레이스 공식 (The Trace Formulas)

저자들은 그들이 **이산 트레이스 공식(Discrete Trace Formulas)**이라 부르는 것을 유도했습니다.

• 개념: 수학에서 "트레이스(trace)"는 시스템 전체의 스냅샷을 찍는 것과 같습니다.
• 공식: 그들은 그래프의 전체 "진동" 또는 "에너지"(고유값의 합)가 폐쇄형 비백트래킹 루프(유턴 없이 시작점과 끝점이 같은 경로)의 수와 직접적으로 같다는 것을 증명했습니다.
• 비유: 드럼을 상상해 보십시오. 드럼이 내는 소리(그의 스펙트럼)는 드럼 가죽의 모양에 의해 결정됩니다. 저자들은 드러머가 스틱을 떼지 않고 가죽 위에 그릴 수 있는 뚜렷하고 반복되지 않는 루프의 개수를 세는 것만으로 드럼의 소리를 계산할 수 있는 방법을 찾아냈습니다.

4. 그들이 증명한 것 (응용 분야)

이 새로운 "번역기"를 사용하여, 저자들은 여러 유명한 결과들을 통합적이고 더 단순한 방식으로 재증명했습니다. 그들은 새로운 물리학을 발명한 것이 아니라, 이 서로 다른 문제들이 사실 동일한 퍼즐을 다른 각도에서 보고 있는 것임을 보여주었습니다.

• 걷기 수 세기 (Counting Walks): 그들은 "일반적인 걷기"를 "비백트래킹 걷기"로 변환함으로써, 지점 A에서 지점 B까지 갈 수 있는 방법의 수를 세는 새롭고 깔끔한 공식을 제시했습니다.
• 열 방정식 (The Heat Equation): 이는 그래프를 통해 열(또는 소문지)이 어떻게 퍼지는지를 모델링합니다. 그들은 열의 확산이 이러한 깔끔한 비백트래킹 경로들의 기여도를 합산함으로써 계산될 수 있음을 보여주었습니다.
• 슈뢰딩거 방정식 (The Schrödinger Equation): 이는 그래프 위에서 움직이는 양자 입자를 모델링합니다. 이 역시 복잡한 양자 행동이 이러한 단순한 비백트래킹 경로들의 합으로 드러난다는 것을 보여줍니다.
• 이하라-바스 정리 (The Ihara-Bass Theorem): 이는 그래프의 구조와 그 "제타 함수"(루프를 인코딩하는 숫자) 사이의 유명한 관계입니다. 저자들은 이 유명한 정리가 로그(logarithm)에 이 새로운 공식을 적용했을 때 나타나는 자연스러운 결과임을 보여주었습니다.

5. "무한한" 도시

그들의 연구가 가진 독특한 특징은, 이 방식이 작은 유한한 도시뿐만 아니라 무한한 도시(끝없는 격자나 무한한 트리 같은 경우)에서도 작동한다는 점입니다.

• 은유: 보통 수학은 무한의 영역에 가면 무너집니다. 하지만 그들이 이 특정한 "타원"과 "비백트래킹" 접근법을 사용했기 때문에, 그들의 공식은 도시가 영원히 계속되더라도 유효합니다.

요약

이 논문은 본질적으로 그래프 이동에 관한 통합 이론입니다.

• 과거의 방식: 가능한 모든 경로를 세려고 시도하다가 백트래킹에 빠지고, 이를 그래프의 진동과 연결하는 데 어려움을 겪음.
• 새로운 방식 (이 논문): 백트래킹을 무시함. 오직 "앞으로 나아가는" 경로에만 집중함. 특별한 수학적 렌즈(홀로모픽 함수 계산법)를 사용하여, 이 깔끔한 경로들이 그래프의 진동, 열 흐름, 그리고 양자 행동을 완벽하게 설명한다는 것을 보여줌.

그들은 단지 하나의 문제를 해결한 것이 아닙니다. 그들은 걷기, 열 흐름, 그리고 양자 역학을 한꺼번에 해결할 수 있는 단일 프레임워크를 구축했으며, 그래프의 "영혼"이 그 비백트래킹 루프 속에 숨겨져 있음을 증명했습니다.

기술 요약

기술 요약: 정규 그래프를 위한 이산 트레이스 공식 및 홀로모픽 함수 계산법

문제 정의
정규 그래프의 스펙트럼 이론은 그래프 상의 보행(walk)의 조합론과 근본적으로 연결되어 있다. 트레이스 방법(trace method)은 인접 행렬 $A$의 스펙트럼을 닫힌 보행(closed walk)의 총 개수와 연관시키지만, 일반적인 보행은 역추적(backtracking)의 존재로 인해 직접 분석하기에는 너무 복면한 경우가 많다. 비역추적 보행(non-backtracking walks)은 더 "단순한" 조합론적 구조를 제공하며, 라마누잔 그래프(Ramanujan graphs) 및 제2 고윳값 추측 연구에서 중요한 역할을 한다. 그러나 쌍곡 곡면에서의 셀베르그 트레이스 공식(Selberg's trace formula)과 유사한 정규 그래프 상의 기존 이산 트레이스 공식들은 역사적으로 정규 트리 상의 회전 불변 함수(rotation-invariant functions)로부터 구성된 함수들로 제한되어 왔다. 이러한 한계는 인접 행렬의 임의의 해석 함수(analytic functions)에 트레이스 공식을 적용하는 것을 저해한다.

방법론
저자들은 $(q+1)$-정규 그래프(무한 그래프 포함)의 인접 행렬 $A$에 적용되는 **홀로모픽 함수 계산법(holomorphic functional calculus)**에 기반한 통합된 프레임워크를 제안한다. 핵심 방법론은 다음과 같다:

1. 체비쇼프형 다항식(Chebyshev-type Polynomials): 저자들은 비역추적 행렬 $A_r$과 본질적으로 관련된 특정 다항식 군 $X_{r,q}(x)$를 활용한다. 프리드먼(Friedman)이 확립한 핵심적인 조합론적 항등식 $A_r = q^{r/2} X_{r,q}(q^{-1/2}A)$가 여기서 사용된다.
2. 주코프스키 변환(Joukowsky Transform) 및 도메인 $\Omega(\rho)$: 분석은 정규화된 인접 행렬 $q^{-1/2}A$의 스펙트럼을 포함하는 복소 평면상의 특정 타원형 도메인 $\Omega(\rho)$ 내에서 수행된다. 이 도메인은 주코프스키 변환 $J(z) = z + z^{-1}$에 의한 환형(annulus)의 상(image)이다.
3. 홀로모픽 전개(Holomorphic Expansion): 코시 적분 공식(Cauchy's integral formula)을 적용함으로써, $\Omega(\rho)$ 상에서 홀로모픽한 임의의 함수 $h$는 체비쇼프형 다항식 $X_{r,q}$의 급수로 전개된다. 이 전개의 계수들은 케스텐-맥케이 분포 $\mu_q$(무한 $(q+1)$-정규 트리의 스펙트럼 측도)에 대한 이 다항식들의 직교성을 사용하여 유도된다.
4. 함수 계산법(Functional Calculus): 이 전개는 $q^{-1/2}A$에 직접 적용되어, $h(q^{-1/2}A)$를 비역추적 행렬 $A_r$들의 무한 급수로 나타내는 결과를 낳는다.

주요 기여 및 결과

• 함수 계산법 공식 (정리 A): 본 논문은 $\Omega(\rho)$ 상에서 홀로모픽한 임의의 함수 $h$에 대한 일반적인 $h(q^{-1/2}A)$ 공식을 확립한다. 이 공식은 연산자를 상수 항(케스텐-맥케이 분포와 관련된 항)과, $h$를 $X_{r,q}$에 대해 적분하여 결정된 계수에 의해 가중치가 부여된 비역추적 행렬들의 무한 급수의 합으로 표현한다.
• 이산 프리 트레이스 공식 (정리 B): 함수 계산법 공식을 특정 정점 $v$에서 평가함으로써, 저자들은 특정 정점에서의 정규 스펙트럼 측도 $\mu_v^G$의 적분을 비역추적 닫힌 보행의 수와 연결하는 프리 트레이스 공식을 유도한다.
• 이산 트레이스 공식 (정리 C): 유한 그래프의 경우, 프리 트레이스 공식을 모든 정점에 대해 합산함으로써 트레이스 공식을 얻는다. 이는 $h$를 그래프의 고윳값들에서 평가한 값의 합을 회로(circuits)(마지막 간선이 첫 번째 간선의 역방향이 아닌 닫힌 비역추적 보행)의 수와 연결한다.
  • 저자들은 이를 **기본 회로(prime circuits)**의 동치류를 사용하여 재구성하였으며, 이는 쌍곡 곡면에서의 셀베르그 트레이스 공식과 구조적으로 유사한 공식을 생성한다.
• 고전적 결과의 통합: 본 프레임워크는 다음과 같은 알려진 결과들에 대한 새로운 기초적 증명과 유도를 제공한다:
  • 보행 계수(Walk Counting): 전체 보행의 수를 비역추적 보행의 수로 표현하는 공식.
  • 이하라-바스 정리(Ihara-Bass Theorem): 로그 함수에 트레이스 공식을 적용함으로써 이하라 제타 함수와 인접 행렬의 행렬식 사이의 관계를 유도함.
  • 열 및 슈뢰딩거 방정식(Heat and Schrödinger Equations): 비역추적 행렬과 베셀 함수(Bessel functions)를 사용하여 정규 그래프 및 격자 상의 열 방정식과 슈뢰딩거 방정식의 명시적인 기본 해(fundamental solutions)를 유도함.
  • 푸리에-라플라스 변환(Fourier-Laplace Transform): 스펙트럼 측도의 푸리에-라플라스 변환에 대한 공식을 얻어, 이를 회로의 수와 연결함.

의의
본 논문은 자신의 주요 의의가 정규 그래프의 인접 행렬을 연구하기 위한 통합된 방법을 제공하는 데 있다고 주장한다. 이전의 트레이스 공식들이 (트리의 기하학적 구조로부터 유도된) 특정 클래스의 함수들로 제한되었던 것과 달리, 본 논문은 특정 타원 위의 임의의 홀로모픽 함수로 그 범위를 확장함으로써 스펙트럼 이론을 더 넓은 범위의 조합론적 문제에 체계적으로 적용할 수 있게 하였다.

이 프레임워크는 스펙트럼 이론과 그래프 조합론 사이의 간극을 메우며, 스펙트럼을 비역추적 보행 및 회로와 체계적으로 연결한다. 이는 격자 상의 보행 계수부터 이하라-바스 정리, 그리고 미분 방정식의 해에 이르기까지, 겉보기에 서로 이질적인 결과들이 단일한 함수 계산 원리로부터 유도될 수 있음을 보여준다. 저자들은 이 접근 방식이 트리 상의 회전 불변 함수로부터 함수를 명시적으로 구성할 필요를 피함으로써, 이산 트레이스 공식의 실용적 효용성을 넓혔음을 강조한다.