Additive energy and Fourier complexity of graphs

Abstract

We study the additive energy and the Fourier approximation of graph adjacency matrices labeled by a cyclic group. For a graph with $N$ vertices, $s$ edges and adjacency matrix $M$, the additive energy of its directed edge set is at most $\min\{(2s)^3,N^2\operatorname{tr}(M^4)\}$, and equality in the spectral bound holds exactly when the labeling attains the graph-energy lower bound for the Fourier ratio. Such a labeling also minimizes every best $k$-term Fourier approximation error, whose square equals the tail of the squared adjacency singular values. We prove that graphs of odd prime-power order admit an equality-attaining labeling exactly when they are cyclic Cayley graphs, and a connected example on $15$ vertices shows that equality need not imply vertex transitivity at other orders. We construct regular graph families with asymptotically maximal normalized additive edge energy and unbounded minimum Fourier ratio, one of them with density tending to one half. For dense graph sequences under uniformly random labelings, the collision dimension differs from the reciprocal squared edge density by a quantity tending to zero in probability. We also prove a quantitative stability estimate for the graph-energy bound and show why its dependence on a spectral scale cannot be omitted, even for regular graphs. For a rank-$m$ orthogonal projector we prove $m\leq D_4\leq\operatorname{FR}^2$, characterize the equality $D_4=m$ by cyclic translation invariance, and obtain a quantitative approximation by a circulant projector.