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,N2tr(M4)}, 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≤ D4≤FR2, characterize the equality D4=m by cyclic translation invariance, and obtain a quantitative approximation by a circulant projector.
Related
- Additive mappings of unweighted directed graphs preserving individual values of the cycle length
- Additive diameters and covering complexity of irreducible representations
- Singular Legendre operators on graphs: trace formulas and Fourier singular support
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
BibTeX
@misc{gupta2026additive,
title = {{Additive energy and Fourier complexity of graphs}},
author = {Vishal Gupta and Sam Ferguson and Alex Iosevich and Joshua Iosevich and Haoyuan Tian and Ben Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31807},
eprint = {2610.31807},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31807},
}
RIS
TY - UNPB
TI - Additive energy and Fourier complexity of graphs
AU - Vishal Gupta
AU - Sam Ferguson
AU - Alex Iosevich
AU - Joshua Iosevich
AU - Haoyuan Tian
AU - Ben Song
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31807
UR - https://arxiv.org/abs/2610.31807
AB - 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^2tr(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≤ D_4≤FR^2, characterize the equality D_4=m by cyclic translation invariance, and obtain a quantitative approximation by a circulant projector.
ER -