2026/06/13 by Vishal Gupta, Alex Iosevich · 1 citation
#math.CO
We study labeling-sensitive Fourier complexity for finite graph kernels. After identifying the vertices of a graph with the cyclic group \mathbb ZN, its adjacency matrix becomes a function on \mathbb ZN2. Minimizing the quotient of the ℓ1 and ℓ2 norms of its two-dimensional Fourier transform over all vertex labelings gives an isomorphism invariant FRmin(G). A nuclear-norm argument gives FRmin(G) ≥ (\mathcal E(G))/(√(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 ZN2. 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(λ), we prove FRmin(Πλ) ≥ √(m(λ)), 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.