2025-11-14T13:52:11.419163

Eigenspace embeddings of imprimitive association schemes

Vidali
For a given symmetric association scheme $\mathcal{A}$ and its eigenspace $S_j$ there exists a mapping of vertices of $\mathcal{A}$ to unit vectors of $S_j$, known as the spherical representation of $\mathcal{A}$ in $S_j$, such that the inner products of these vectors only depend on the relation between the corresponding vertices; furthermore, these inner products only depend on the parameters of $\mathcal{A}$. We consider parameters of imprimitive association schemes listed as open cases in the list of parameters for quotient-polynomial graphs recently published by Herman and Maleki, and study embeddings of their substructures into some eigenspaces consistent with spherical representations of the putative association schemes. Using this, we obtain nonexistence for two parameter sets for $4$-class association schemes and one parameter sets for a $5$-class association scheme passing all previously known feasibility conditions, as well as uniqueness for two parameter sets for $5$-class association schemes.
academic

Eigenspace embeddings of imprimitive association schemes

基本信息

  • 论文ID: 2504.08733
  • 标题: Eigenspace embeddings of imprimitive association schemes
  • 作者: Janoš Vidali (University of Ljubljana, Slovenia)
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月16日提交至arXiv
  • 论文链接: https://arxiv.org/abs/2504.08733

摘要

对于给定的对称结合方案A\mathcal{A}及其特征空间SjS_j，存在一个将A\mathcal{A}的顶点映射到SjS_j中单位向量的映射，称为A\mathcal{A}在SjS_j中的球面表示，使得这些向量的内积仅依赖于对应顶点之间的关系；此外，这些内积仅依赖于A\mathcal{A}的参数。本文考虑Herman和Maleki最近发表的商多项式图参数列表中列为开放案例的非本原结合方案参数，研究其子结构嵌入到某些特征空间的问题，这些嵌入与假定结合方案的球面表示一致。利用这种方法，我们证明了两个通过所有已知可行性条件的4类结合方案参数集和一个5类结合方案参数集的不存在性，以及两个5类结合方案参数集的唯一性。

研究背景与动机

  1. 要解决的问题：本文研究结合方案(association schemes)的存在性和唯一性问题，特别关注非本原结合方案。结合方案是组合数学中的重要对象，其分类一直是一个广泛开放的问题。
  2. 问题的重要性：结合方案是编码理论、设计理论和有限几何等多个领域的基础结构。完整分类这些对象对理解这些领域的基本结构具有重要意义。即使对于强正则图(2类结合方案)和距离正则图等特殊子族，完整分类仍然是开放问题。
  3. 现有方法的局限性：传统的可行性条件(如握手引理、绝对界限、Krein参数非负性等)虽然必要，但不充分。许多参数集通过了所有已知的可行性检验，但实际上对应的结合方案并不存在。
  4. 研究动机：作者开发了一种新的技术——特征空间嵌入方法，通过研究结合方案在其特征空间中的球面表示来判断参数集的可行性。这种方法特别适用于非本原结合方案，因为它们具有较小的子结构可供分析。

核心贡献

  1. 开发了特征空间嵌入技术：提出了一种通过研究结合方案子结构在特征空间中的嵌入来判断参数集可行性的新方法。
  2. 证明了三个不存在性结果：
    • 两个4类结合方案参数集：[[12, 4, 4, 24], 6, 0, 3; 0, 1; 2]和[[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]
    • 一个5类结合方案参数集：[[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]
  3. 证明了两个唯一性结果：
    • 5类结合方案参数集[[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]
    • 5类结合方案参数集[[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]
  4. 开发了配套软件工具：基于SageMath开发了eigenspace-embeddings软件包，实现了相关算法。
  5. 系统分析了Herman-Maleki数据库：对商多项式图参数数据库进行了全面的可行性检验，识别了大量不可行的参数集。

方法详解

任务定义

给定结合方案的参数集，判断是否存在具有这些参数的结合方案，如果存在，确定其唯一性。输入是交集数、特征矩阵或对偶特征矩阵等参数，输出是存在性/唯一性的判断。

模型架构

1. 球面表示理论基础

对于结合方案A=(X,R)A = (X, R)及其特征空间SjS_j，定义球面表示：

  • 将每个顶点x∈Xx \in X映射为单位向量ux=nmjEj1xu_x = \sqrt{\frac{n}{m_j}}E_j 1_x
  • 对于关系(x,y)∈Ri(x,y) \in R_i，有⟨ux,uy⟩=Qijmj\langle u_x, u_y \rangle = \frac{Q_{ij}}{m_j}

2. 算法1：特征空间嵌入算法

输入: 特征空间索引j，关系矩阵C
输出: 单位向量系数矩阵U或失败
for x = 1 to n' do
    h ← 1
    for y = 1 to x-1 do
        d ← C_xy - Σ(k=1 to h-1) a_xk * a_yk
        if h ≤ m_j ∧ a_yh ≠ 0 then
            a_xh ← d/a_yh; h ← h+1
        else if d ≠ 0 then fail
    计算||u_x||²并验证等于1

3. 非本原结合方案的特殊结构

对于具有非平凡本原集0~\tilde{0}的非本原结合方案：

  • 顶点集被划分为等价类{Xℓ}\{X_\ell\}
  • 每个等价类上的导出子方案具有相同参数
  • 利用这种结构可以分析较小的子结构

技术创新点

  1. 特征空间约束：通过要求子结构能够嵌入到特征空间中，提供了比传统方法更强的约束。
  2. 分层构造策略：从小的子结构开始，逐步扩展，在每一步检验嵌入的存在性。
  3. 计算代数方法：使用扩展的数域FFF\sqrt{F}进行精确计算，避免了符号计算的复杂性。
  4. 引理2的应用：对于特定类型的非本原方案，证明了子结构之间连接的限制性，大大减少了需要检验的情况数。

实验设置

数据集

  • Herman-Maleki数据库：包含3-6类商多项式图的参数数组
  • Hanaki-Miyamoto分类：小顶点数结合方案的完整分类
  • 已知构造：来自各种代数和几何构造的结合方案

评价指标

  • 参数集的可行性(通过/不通过已知条件)
  • 存在性(存在/不存在对应的结合方案)
  • 唯一性(唯一/多个非同构的方案)

对比方法

传统可行性条件：

  • 握手引理
  • 重数的整数性
  • Krein参数非负性
  • 绝对界限
  • 禁止四元组条件
  • 商方案的可行性

实现细节

  • 基于SageMath计算机代数系统
  • 使用PARI进行数域计算
  • 使用nauty进行图生成和同构检验
  • 使用GLPK进行整数线性规划(图着色)

实验结果

主要结果

不存在性结果

  1. QPG [[12, 4, 4, 24], 6, 0, 3; 0, 1; 2]：
    • 45个顶点的4类方案
    • 通过引理2分析子结构连接模式
    • 发现只有一种可能的3-团构型能嵌入S1S_1
    • 但无法找到剩余顶点的有效嵌入
  2. QPG [[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]：
    • 考虑了100种可能的子方案构型
    • 每种情况都检验了8000个候选顶点
    • 均未找到有效的单位向量表示
  3. QPG [[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]：
    • 5类方案，45个顶点
    • 通过图生成找到18种可能的双分图
    • 其中7种允许嵌入到2维子空间，但扩展到3-团时均失败

唯一性结果

  1. QPG [[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]：
    • 40个顶点的5类方案
    • 通过S1S_1中的球面表示完全确定了结构
    • 证明了这是唯一的具有这些参数的结合方案
  2. QPG [[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]：
    • 45个顶点的5类方案
    • 可以用环面Z5×Z3×Z3Z_5 \times Z_3 \times Z_3上的Cayley图描述
    • 自同构群的阶为77760

消融实验

论文通过系统性地分析不同维数的特征空间验证了方法的有效性：

  • 当mjmˉjˉ>3\frac{m_j}{\bar{m}_{\bar{j}}} > 3时，约束通常不够强
  • 当mjmˉjˉ≤3\frac{m_j}{\bar{m}_{\bar{j}}} \leq 3时，特别是≤52\leq \frac{5}{2}时，约束变得非常严格

案例分析

作者提供了一个小例子(8个顶点的3类方案)来说明方法：

  • 构造了单位向量系数矩阵UU
  • 通过内积重构了关系矩阵
  • 验证了这确实对应于3-立方体Q3Q_3的结合方案

相关工作

主要研究方向

  1. 结合方案分类：Brouwer等人对强正则图和距离正则图的参数表，Van Dam对3类方案的研究
  2. 球面表示应用：Bannai等人用于球面码的唯一性证明，Gavrilyuk和Suda的相关工作
  3. 商多项式图理论：Fiol的原始工作，Herman和Maleki的参数数据库

本文的优势

  • 首次将球面表示系统性地应用于非本原结合方案的可行性研究
  • 开发了高效的计算方法和软件工具
  • 解决了多个长期开放的参数集问题

结论与讨论

主要结论

  1. 特征空间嵌入方法为研究结合方案提供了强有力的新工具
  2. 许多通过传统可行性条件的参数集实际上不可行
  3. 对于某些参数集，可以证明对应结合方案的唯一性

局限性

  1. 计算复杂性：方法的计算成本随顶点数指数增长
  2. 适用范围：主要适用于非本原方案，对本原方案效果有限
  3. 维数限制：需要特征空间维数相对较小才有效

未来方向

  1. 扩展到更大规模的问题
  2. 开发更高效的算法
  3. 应用于其他类型的组合结构
  4. 与机器学习方法结合

深度评价

优点

  1. 方法创新性：首次系统性地将球面表示用于结合方案可行性研究，提供了全新的分析角度
  2. 理论贡献：解决了多个具体的开放问题，推进了该领域的发展
  3. 实现完整性：提供了完整的软件实现，增强了结果的可复现性
  4. 分析深度：对Herman-Maleki数据库的系统分析提供了该领域的全面视图

不足

  1. 可扩展性限制：方法的计算复杂性限制了其应用于大规模问题
  2. 理论分析不足：缺乏对方法适用条件的理论刻画
  3. 通用性问题：主要针对特定类型的非本原方案，通用性有待提高

影响力

  1. 学术价值：为结合方案理论提供了新的研究工具和方法
  2. 实用价值：软件工具可被其他研究者使用
  3. 领域推进：解决了具体问题，推动了该领域的发展

适用场景

  • 小到中等规模的非本原结合方案分析
  • 商多项式图的存在性和唯一性研究
  • 编码理论和设计理论中的相关问题
  • 有限几何中的关联结构研究

参考文献

论文引用了39篇重要文献，涵盖了结合方案理论、球面表示、计算方法等多个方面，其中关键文献包括：

  • Brouwer, Cohen, Neumaier的经典教材《Distance-regular graphs》
  • Bannai等人关于球面表示唯一性的开创性工作
  • Herman和Maleki关于商多项式图参数的最新研究
  • Delsarte关于结合方案代数方法的奠基性工作