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

本文引入了一个利用特定椭圆上的全纯泛函演算将正则图的邻接矩阵按非回溯矩阵进行展开的统一框架，从而推导出将谱理论与图组合学联系起来的离散迹公式，并为诸如行走计数、Ihara-Bass 公式以及基于图的热方程和薛定谔方程等问题提供了新的证明。

要点

想象一个完全由交叉路口（顶点）和单向街道（边）组成的城市。在数学中，这被称为一个图（graph）。现在，想象这座城市中的每个交叉路口都有相同数量的道路通向外部。这是一个正则图（regular graph）。

本文作者 Gong、Li 和 Liu 构建了一个全新的“通用翻译器”来理解这些城市。他们的目标是将观察城市的两种截然不同的方式联系起来：

1. 谱视角（The Spectral View）： 通过城市的“振动”或频率（数学上即邻接矩阵的特征值）来观察城市。
2. 行走视角（The Walking View）： 计数人们可以在街道中实际行走的路径。

以下是他们发现的简单拆解，使用了日常类比。

1. 问题所在：“回溯”带来的混乱

如果你问：“从交叉路口 A 到交叉路口 B 走 10 步有多少种走法？”答案通常是一个巨大且复杂的数字。为什么？因为大多数这些行走都涉及回溯（backtracking）。

• 回溯： 你走下街道，意识到自己犯了错，然后立即转身原路返回。
• 混乱： 在一座大城市中，这些“前进后立即后退”的路径数量是压倒性的且极其混乱。这就像试图在浓雾中统计一个人在漫无目的地游荡时所走的每一步。

作者们关注的是非回溯行走（Non-Backtracking Walks）。这些路径是指你永远不会立即转身返回原路。你向前走，左转，右转，但绝不会在紧接着的一步中做 U 型转弯。

• 类比： 想象一位一心想要参观新景点的游客，他拒绝立即重复刚才的脚步。他们的路径要“干净”得多，也更容易追踪。

2. 解决方案：一个特殊的“翻译器”（全纯泛函演算）

作者们使用了一种名为**全纯泛函演算（holomorphic functional calculus）**的高级数学工具。

• 隐喻： 想象你有一个复杂的机器（图的邻接矩阵）正在处理数据。通常，为了理解这个机器对特定输入（如热方程或波）的处理方式，你必须解决一个困难的谜题。
• 创新之处： 作者们发现了一种方法，可以通过一个特殊的数学景观中的椭圆（ellipse），直接将任何光滑、行为良好的函数（如波或热模式）“插入”到这台机器中。
• 结果： 他们的这种方法并没有得到一个混乱且无法求解的方程，而是将答案展开成了一系列整齐的**非回溯矩阵（Non-Backtracking Matrices）**的无穷级数。

可以这样想：与其通过追踪每个人的不规则移动来描述混乱的人群，他们意识到，如果只追踪那些直线行走而不折返的人，就可以完美地重建整个群体的行为。

3. 核心发现：迹公式（Trace Formulas）

论文推导出了他们称之为**离散迹公式（Discrete Trace Formulas）**的内容。

• 概念： 数学中的“迹（trace）”就像是对整个系统进行一次快照。
• 公式： 他们证明了图的总“振动”或“能量”（特征值的总和）直接等于闭合非回溯环路（即在不进行 U 型转弯的情况下，从起点出发并回到起点的路径）的数量。
• 类比： 想象一面鼓。鼓发出的声音（其谱）是由鼓皮的形状决定的。作者们发现了一种方法，只需通过计算鼓手在不抬起鼓棒的情况下，能在鼓皮上描绘出多少个不同的、非重复的环路，就能计算出鼓的声音。

4. 他们证明了什么（应用）

利用这个新的“翻译器”，作者们以一种统一且更简单的方式重新证明了几个著名的结论。他们并非发明了新的物理学，而是展示了这些不同的问题实际上是从不同角度观察同一个谜题。

• 计数行走： 他们给出了一个简洁的新公式来计算从点 A 到点 B 的行走方式，方法是将混乱的“一般行走”转换为“非回溯行走”。
• 热方程： 这模拟了热量（或谣言）如何在图中传播。他们展示了热量的扩散可以通过累加这些干净的非回溯路径的贡献来计算。
• 薛定谔方程： 这模拟了量子粒子在图上的运动。同样，复杂的量子行为被揭示为这些简单的非回溯路径之和。
• Ihara-Bass 定理： 这是关于图的结构与其“Zeta 函数”（一个编码图环路的数值）之间著名的关系。作者们展示了当该定理应用于对数时，这个著名的定理正是他们新公式的一个自然结果。

5. “无限”城市

他们工作的一个独特之处在于，它不仅适用于小型有限城市，也适用于无限城市（如无限网格或无限树）。

• 隐喻： 通常，数学在面对“无限”时会失效。但由于他们使用了这种特定的“椭圆”和“非回溯”方法，即使城市向无穷远处延伸，他们的公式依然成立。

总结

这篇论文本质上是一套图运动的统一理论。

• 旧方法： 试图计算每条可能的路径，陷入回溯的泥潭，并难以将其与图的振动联系起来。
• 新方法（本文）： 忽略回溯。只关注“向前移动”的路径。利用一种特殊的数学透镜（全纯演算）来证明，这些干净的路径可以完美地解释图的振动、热流和量子行为。

他们不仅仅是解决了一个问题；他们构建了一个单一的框架，可以同时解决图上的计数、热流和量子力学问题，证明了图的“灵魂”就隐藏在它的非回溯环路之中。

技术摘要

技术摘要：正则图的离散迹公式与全纯泛函演算

问题陈述
正则图的谱理论在本质上与图上游走的组合学密切相关。虽然迹方法将邻接矩阵 $A$ 的谱与闭游走的总数联系起来，但由于回溯（backtracking）的存在，一般的游走往往过于复杂而难以直接分析。非回溯游走提供了一种“更简单”的组合结构，在 Ramanujan 图和第二特征值猜想的研究中发挥着至关重要的作用。然而，现有的正则图离散迹公式（类似于双曲曲面上 Selberg 的迹公式）在历史上一直局限于由正则树上的旋转不变函数构造的函数。这种局限性阻碍了将迹公式应用于邻接矩阵的任意解析函数。

方法论
作者提出了一个基于应用于 $(q+1)$-正则图（包括无限图）的邻接矩阵 $A$ 的**全纯泛函演算（holomorphic functional calculus）**的统一框架。其核心方法论包括：

1. 切比雪夫型多项式： 作者利用了一类特定的多项式 $X_{r,q}(x)$，这类多项式与非回溯矩阵 $A_r$ 有着内在联系。文中利用了 Friedman 建立的一个关键组合恒等式：$A_r = q^{r/2} X_{r,q}(q^{-1/2}A)$。
2. Joukowsky 变换与定义域 $\Omega(\rho)$： 分析是在复平面内一个特定的定义域 $\Omega(\rho)$ 内进行的，该定义域是一个包含归一化邻接矩阵 $q^{-1/2}A$ 谱的椭圆。该定义域是环域在 Joukowsky 变换 $J(z) = z + z^{-1}$ 下的像。
3. 全纯展开： 通过应用 Cauchy 积分公式，任何在 $\Omega(\rho)$ 上全纯的函数 $h$ 都可以展开为切比雪夫型多项式 $X_{r,q}$ 的级数。该展开的系数是通过这些多项式相对于 Kesten-McKay 分布 $\mu_q$（无限 $(q+1)$-正则树的谱测度）的正交性推导出来的。
4. 泛函演算： 该展开被直接应用于算子 $q^{-1/2}A$，从而得到 $h(q^{-1/2}A)$ 关于非回溯矩阵 $A_r$ 的展开式。

主要贡献与结果

• 泛函演算公式（定理 A）： 文中为任何在 $\Omega(\rho)$ 上全纯的函数 $h$ 建立了通用的 $h(q^{-1/2}A)$ 公式。该公式将算子表示为一个常数项（涉及 Kesten-McKay 分布）加上一系列由 $h$ 对 $X_{r,q}$ 的积分所决定的权重系数组成的非回溯矩阵之和。
• 离散预迹公式（定理 B）： 通过在特定顶点 $v$ 处评估泛函演算公式，作者推导出了一个预迹公式。该公式将 $h$ 对顶点处的归一化谱测度 $\mu_v^G$ 的积分，与从 $v$ 出发并回到 $v$ 的闭非回溯游走的数量联系起来。
• 离散迹公式（定理 C）： 对于有限图，通过对所有顶点求和预迹公式，作者得到了一个迹公式。该公式将 $h$ 在图特征值上的求和，与回路（circuits）（即最后一条边不是第一条边的逆边的闭非回溯游走）的数量联系起来。
  • 作者通过使用**素回路（prime circuits）**的等价类对该公式进行了重构，使其在结构上类似于双曲曲面上的 Selberg 迹公式。
• 统一经典结果： 该框架为若干已知结果提供了新的、初等的证明和推导：
  • 游走计数： 一个将总游走数表示为非回溯游走之和的公式。
  • Ihara-Bass 定理： 通过对对数函数应用迹公式，推导出了 Ihara Zeta 函数与邻接矩阵行列式之间的关系。
  • 热方程与薛定谔方程： 推导出了正则图和晶格上热方程与薛定谔方程的显式基本解，其形式包含非回溯矩阵和贝塞尔函数。
  • 傅里叶-拉普拉斯变换： 得到了谱测度的傅里叶-拉普拉斯变换公式，将其与回路的数量联系起来。

意义
该论文声称其主要意义在于提供了一种研究正则图邻接矩阵的统一方法。通过将以往的迹公式（受限于由树几何构造的特定类函数）推广到任何在特定椭圆上全纯的函数，作者使得将谱理论系统地应用于更广泛的组合问题成为可能。

该框架通过系统地将谱与非回溯游走及回路联系起来，弥合了谱理论与图组合学之间的鸿沟。它表明，从晶格上的游走计数到 Ihara-Bass 定理以及微分方程的解，这些看似迥异的结果都可以从单一的泛函演算原理中推导出来。作者强调，这种方法避免了需要显式地从树上的旋转不变函数构造函数，从而扩大了离散迹公式的实际应用价值。