Fourier Ratios of Graph Kernels: Energy Bounds, Optimal Labelings, and Recovery

We study labeling-sensitive Fourier complexity for finite graph kernels. After identifying the vertices of a graph with the cyclic group ${\mathbb{Z}}_N$, its adjacency matrix becomes a function on ${\mathbb{Z}}_N^2$. Minimizing the quotient of the ${\mathrm{\ell }}^1$ and ${\mathrm{\ell }}^2$ norms of its two-dimensional Fourier transform over all vertex labelings gives an isomorphism invariant ${\mathrm{FR}}_{\min }(G)$. A nuclear-norm argument gives $${\mathrm{FR}}_{\min }(G)\ge \frac{\mathcal{E}(G)}{\sqrt{2s}},$$ where $s$ is the number of edges and $\mathcal{E}(G)$ is the graph energy. The natural cyclic labeling attains equality for every circulant graph. We obtain exact formulas for several graph families and a labeling-sensitive complete bipartite example. We also connect the invariant with the Fourier algebra of ${\mathbb{Z}}_N^2$. The quantitative Cohen idempotent theorem implies that every Boolean kernel of bounded Fourier ratio has an exact signed coset decomposition whose length is independent of $N$. A previously established Fourier-ratio recovery theorem gives stable Frobenius approximation of a fixed labeled adjacency matrix from Bernoulli samples. We distinguish this conclusion from exact edge recovery and from the problem of finding a good labeling. For a Laplacian eigenvalue of multiplicity $m(\lambda )$, we prove $${\mathrm{FR}}_{\min }({\mathrm{\Pi }}_{\lambda })\ge \sqrt{m(\lambda )},$$ with equality for circulant graphs. Strongly regular graphs and the Petersen graph show how adjacency and projector complexity can agree or differ. Direct projector sampling yields heat-kernel approximation. We conclude with a graph-signal spectral synthesis principle and asymptotic uniqueness from incomplete vertex data.