Uniform adjacency-degree probes from differential rigidity
Abstract
We construct a fixed triangular family of noncommutative polynomials that spans the joint cyclic module of a real symmetric pair from any prescribed vector. In dimension at most N, when the second matrix has spectral diameter at most N−1, the family has N(N+1)/2 members, degree at most N−1, and a shared arithmetic circuit of size O(N2). No rank-dependent choice of coefficients is made. The proof uses a rational differential connection with a small self-adjoint residue: a primitive polynomial exterior vector for an invariant subspace must have an integer degree smaller than one. For connected trees, the probes and the pointed adjacency--degree reconstruction theorem give one explicit self-adjoint polynomial pN∈ℤ⟨ a,d⟩ whose trace separates all trees of order at most N. Its circuit has O(N2) gates, formal degree at most 3N−2, and polynomial bit complexity. Only the original adjacency and degree matrices, the identity, and ordinary matrix arithmetic are used. A separate integer sum-of-squares construction gives a fixed positive semidefinite representative on which the all-one vector is cyclic; its degree is O(N2). A linear trace-degree lower bound shows that the first construction has the correct asymptotic degree scale.
Related
- Positive cubature on S2:low-degree rigidity and uniform bounds
- A Unified Spectral Framework for Weighted Adjacency-Degree Matrices of Dendrimer and Bethe Trees
- Adjacency-degree algebras and spectral determination of graphs
- Degree Adjacency Diametrical Matrix of Graphs Spectral Properties and Energy Bounds
- Punctured adjacency-degree algebras of Cartesian products
BibTeX
@misc{lu2026uniform,
title = {{Uniform adjacency-degree probes from differential rigidity}},
author = {Zhipeng Lu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18901},
eprint = {2610.18901},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18901},
}
RIS
TY - UNPB
TI - Uniform adjacency-degree probes from differential rigidity
AU - Zhipeng Lu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.18901
UR - https://arxiv.org/abs/2610.18901
AB - We construct a fixed triangular family of noncommutative polynomials that spans the joint cyclic module of a real symmetric pair from any prescribed vector. In dimension at most N, when the second matrix has spectral diameter at most N−1, the family has N(N+1)/2 members, degree at most N−1, and a shared arithmetic circuit of size O(N^2). No rank-dependent choice of coefficients is made. The proof uses a rational differential connection with a small self-adjoint residue: a primitive polynomial exterior vector for an invariant subspace must have an integer degree smaller than one. For connected trees, the probes and the pointed adjacency--degree reconstruction theorem give one explicit self-adjoint polynomial p_N∈ℤ⟨ a,d⟩ whose trace separates all trees of order at most N. Its circuit has O(N^2) gates, formal degree at most 3N−2, and polynomial bit complexity. Only the original adjacency and degree matrices, the identity, and ordinary matrix arithmetic are used. A separate integer sum-of-squares construction gives a fixed positive semidefinite representative on which the all-one vector is cyclic; its degree is O(N^2). A linear trace-degree lower bound shows that the first construction has the correct asymptotic degree scale.
ER -