We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple frequency channels and corrupted by Gaussian noise. Using the framework of \emph{ low-degree polynomial algorithms}, we analyze the task of estimating the structured signal in such observations. We show that, assuming the low-degree heuristic, in synchronization models over the circle group $\mathsf{ SO}(2)$, a simple spectral method is computationally optimal among all polynomial-time estimators when the number of frequencies satisfies $L=n^{ o(1)}$. This significantly extends prior work \cite{ KBK24+}, which only applied to a fixed constant number of frequencies. Together with known upper bounds on the statistical threshold \cite{ PWBM18a}, our results establish the existence of a \emph{ statistical-to-computational gap} in this model when the number of frequencies is sufficiently large.
Categories: math.ST cs.DS math.PR stat.TH