Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions

We study high-dimensional random geometric graphs (RGGs) of edge-density p with vertices uniformly distributed on the d-dimensional torus and edges inserted between sufficiently close vertices with respect to an Lq-norm. We focus on distinguishing an RGG from an Erdős--Rényi (ER) graph if both models have edge probability p. So far, most results considered either spherical RGGs with L₂-distance or toroidal RGGs under L_-distance. However, for general Lq-distances, many questions remain open, especially if p is allowed to depend on n. The main reason for this is that RGGs under Lq-distances can not easily be represented as the logical AND of their 1-dimensional counterparts, as for L_ geometries. To overcome this, we devise a novel technique for quantifying the dependence between edges based on modified Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general Lq norms from ER-graphs for fixed p and q. We achieve this by showing that signed triangles can distinguish the two models when d n³p³ for the whole regime of c/n<p<1. Additionally, our technique yields an improved information-theoretic lower bound for this task, showing that the two distributions converge whenever d=Ω (n³p²), which is just as strong as the currently best known lower bound for spherical RGGs in case of general p from Liu et al. STOC'22. Finally, our expansions allow us to tightly characterize the spectral properties of toroidal RGGs both under Lq-distances for fixed 1 q<, and L_-distance. Our results partially resolve a conjecture of Bangachev and Bresler COLT'24 and prove that the distance metric, rather than the underlying space, is responsible for the observed differences in the behavior of spherical and toroidal RGGs.