Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

技術要約：強正則グラフにおける一様平均混合のためのモーメント法

問題設定
本論文は、連結な非完全強正則グラフ（SRG）における連続時間量子ウォークの「一様平均混合（Uniform Average Mixing, UAM）」の存在について調査している。UAMは、混合行列の時刻平均が一様行列 $\frac{1}{n}J$（ここで $n$ は頂点数）に等しくなるような、$[0, \infty)$ 上のボレル確率測度 $\mu$ の存在によって定義される。具体的には、どのようなSRGがこのような法則を許容するかを決定し、それらの法則の性質（例：有界な密度を持つか、有限の原子測度を持つか、あるいは単一の観測時刻を持つか）を特徴付けることを目的としている。本研究は、量子ウォークの平均に関するスペクトル・モーメントの視点を扱っており、これは先行研究において未解決の問題として提起されていたものである。

手法
著者はスペクトル・モーメント法を用い、無限次元の時刻法則の探索問題を有限次元のモーメント問題へと還元している。

1. スペクトル還元: SRGの代数的構造（具体的には $A^2 = (\lambda - \nu)A + (k - \nu)I + \nu J$ という恒等式）を利用して、混合行列 $M(t)$ をグラフの制限固有値に対応する3つの余弦モーメントを用いて表現する。
2. アフィン制約: UAMの条件は、これら3つのモーメントに対する2つのアフィン制約を満たすことと同値であると示され、これにより $\mathbb{R}^3$ 内に「モーメント線」が定義される。
3. 幾何学的および代数的ツール:
   • カラテオドリ型の定理: 著者はカラテオドリの定理の洗練された手法を用いて、元の時刻法則に関わらず、あらゆる平均混合行列が最大でも2つの観測時刻（原子）によって実現可能であることを証明している。
   • モーメント問題: 非整数スペクトルを持つグラフに対して、著者はフェイェール多項式とグラム行列の逆行列を用いて、有界かつコンパクトな台を持つ明示的な時刻密度を構成している。整数スペクトルの場合、有限のトプリッツおよびハンケル半正定値行列を用いた必要十分条件を導出している。
   • 複素アダマール行列: グラフのボーズ・メスナー代数内にある正定値グラム行列上の点が存在することと、複素アダマール行列の存在との関連付けが重要なステップとなる。これにより、事前の分類定理やコンピュータ計算に頼ることなく、パラメータ集合の分類が可能となる。

主な貢献と結果

• 2時刻への還元: 本論文は、連結な非完全SRGにおいて、もしUAMの法則が存在するならば、それは最大でも2つの原子（観測時刻）を持つ離散測度によって実現可能であることを証明している。これにより、UAMの探索は特定の時刻のペアを確認することへと簡略化される。
• 明示的な構成:
  • 非整数制限固有値を持つSRG（非平方次数のコンファレンス・グラフ）に対して、著者は有限区間 $[0, T]$ に支持される有界な確率密度を構成している。
  • 整数スペクトルの場合、存在を判定するための有限の半正定値基準（トプリッツ/ハンケル形式）が提供されている。
• 完全な分類: 本論文は、UAMを許容するすべてのSRGを特定している。瞬間的一様混合（IUM）およびコンファレンス・グラフ（非平方次数）を除くと、UAMは以下のグラフ（またはその補グラフ）によってのみ許容される：
  1. パラメータ $(4\theta^2 + 4\theta + 2, 2\theta^2 + \theta, \theta^2 - 1, \theta^2)$ を持つグラフ（またはその補グラフ）、ここで $\theta \ge 1$。
  2. パラメータ $(4\theta^2 - 1, 2\theta^2, \theta^2, \theta^2)$ を持つグラフ（またはその補グラフ）、ここで $\theta \ge 2$。
  • ペーターセン・グラフとその補グラフは、これらのファミリーの最小構成要素として特定されている。
• 密度 vs 原子: 二分法が確立されている。UAMを持つグラフが有界な時刻密度を持つための必要十分条件は、それが瞬間的一様混合（IUM）を許容しないことである。もしIUMが存在する場合、UAMの法則は離散的な集合上に集中していなければならない。
• 先行研究の修正: 本論文は、Godsil, Mullin, および Roy によるSRG上の瞬間的一様混合の分類を修正している。彼らの符号条件は、半分にされた5次立方体（$t=\pi/4$ で一様混合する）を誤って除外しており、また、UAMが存在しないパラメータ $(36, 14, 4, 6)$ を誤って含んでいたことを指摘している。修正された分類は、$n$ が16で割り切れること、および特定のハダマール行列の存在に基づいている。

意義および主張
本論文は、一様平均混合を許容する強正則グラフの完全かつ自己完結的な分類を提供すると主張している。その意義は以下の点にある：

• 統一: UAMの研究を、複素アダマール行列のボーズ・メスナー代数内での理論と統合し、この文脈におけるChanによる分類の簡潔かつ初等的な証明を提供している。
• 正確性: 整数スペクトルのケースに対しては厳密な非漸近的基準（有限半正定値条件）を、非整数ケースに対しては明示的な構成を提供している。
• 未解決問題の解決: 混合時間の有理性と、SRGのクラス内におけるIUMのスペクトル条件に関する特定の未解決問題に回答している。
• 手法の厳密性: 分類は、コンピュータ計算や事前の分類定理に依存することなく、初等的な不等式とモーメント論のみを用いて導出されている。

著者は、これらの結果が連結な非完全SRGのクラスに対して決定的であることを強調しており、連続的な密度を持つグラフ、離散的な原子法則を必要とするグラフ、そして一様平均混合を全く許容しないグラフの間の正確な境界を確立している。