arXiv:2610.10017
Moment Methods for Uniform Average Mixing on Strongly Regular Graphs
Musung Kang
Abstract
We study continuous-time quantum walks on connected strongly regular graphs that are not complete, observed at a random time drawn from a freely chosen probability law. Uniform average mixing (UAM) asks for a law under which every averaged transition probability equals $1/n$, where $n$ is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved $5$-cube, which mixes uniformly at time $π/4$. With the order $4θ^2$ read literally, its parity condition also excludes the Clebsch graph and includes the parameters $(36,14,4,6)$, for which no time law gives uniform average mixing.
AI Summary
The paper classifies uniform average mixing (UAM) for connected, noncomplete strongly regular graphs: whether a freely chosen observation-time probability law makes every averaged continuous-time quantum-walk transition probability equal to $1/n$. This differs from long-time uniform averaging. UAM reduces to two affine constraints on three cosine moments of eigenvalue gaps. For integral spectra, realizability is characterized exactly by a finite positive-semidefinite Toeplitz completion, with equivalent Hankel conditions and measure recovery. Every averaged mixing matrix—not just a uniform one—can be reproduced using at most two observation times, retaining any compact support interval. The classification includes nonsquare-order conference graphs, conference graphs of order nine, $C_4$, and the instantaneous-uniform-mixing Hadamard families with $16\mid n$. Additional UAM graphs have parameters $(4\theta^2+4\theta+2,2\theta^2+\theta,\theta^2-1,\theta^2)$ for $\theta\ge1$, or $(4\theta^2-1,2\theta^2,\theta^2,\theta^2)$ for $\theta\ge2$, or complementary parameters. Exactly two times are needed outside the instantaneous-mixing cases. Nonsquare conference graphs receive explicit bounded densities supported within $[0,40(n^2-4n+5)]$; among UAM graphs, bounded densities exist exactly when instantaneous mixing does not. The proofs combine convex-curve support reduction, trigonometric moment theory, arithmetic obstructions, and three inequalities linking moment feasibility to complex Hadamard matrices. They also correct sign and parity conditions in an existing instantaneous-mixing classification. The two-time compression need not preserve all three moments and supplies no general uniform time bound; the density-support bound is sufficient, not optimized.
The model also proposed the arguments of Lemma~\ref{lem:observable-compression}, Remarks~\ref{rem:two-scope} and~\ref{rem:conference-explicit} and Propositions~\ref{prop:elementary-chan}, \ref{prop:no-single-time} and~\ref{prop:density}.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 26 pages, 1 table. Includes a correction of Theorem 5.1 and Lemma 5.2 in arXiv:1301.5889