Randomstrasse101 Open Problems (2024) — Problem 6

Definitions and mathematical statement

Let $G$ be either \[ SO(2)=\{R\in{\mathbb{R}}^{2\times2}:R^{\mathsf T}R=I_2,\ \det R=1\} \] or a finite group. Uniform sampling of a group element means normalized Haar measure when $G=SO(2)$, and the probability measure assigning mass $1/|G|$ to each element when $G$ is finite. The supplied record says that the signal $x$ is sampled uniformly over group elements; it does not specify the space containing the entire signal or the joint distribution of any signal coordinates.

Source-level target. For the synchronization model over $G$, find a scaling $L=L_n$ of the number of frequencies such that there is a polynomial-time algorithm that reliably detects the signal as $n\to\infty$, for every signal-strength parameter satisfying \[ \lambda>\lambda_{\mathrm{comp},L}, \qquad \lambda_{\mathrm{comp},L}<1. \] Here $n$ is the asymptotic size parameter, $L$ counts the frequencies, and $\lambda_{\mathrm{comp},L}$ denotes the computational threshold sought in the source. Their precise model-dependent meanings are not supplied.

Unresolved qualifications. The record gives no observation equation, noise law, normalization of $\lambda$, definition of the frequencies, null hypothesis, or error criterion for reliable detection. It also leaves unspecified whether the finite group is fixed or varies with $n$, and how its available frequencies constrain $L_n$. Thus the displayed request is an incomplete formulation, not a fully specified statistical problem. When $L=L_n$ varies, the quantifiers governing $\lambda>\lambda_{\mathrm{comp},L_n}$, and whether the threshold stays uniformly below $1$, require clarification. Polynomial running time likewise requires a specified input representation and size. These missing qualifications prevent a unique precise completion from the supplied record.

Short English statement

Find a scaling of the number of frequencies that permits polynomial-time reliable detection below signal strength $1$ in group synchronization over $SO(2)$ or a finite group, with a uniformly sampled signal. The supplied record labels this problem open, but omits the observation model and several quantifiers needed for a precise statement.

Sources

• Local UnsolvedMath registry, permanent ID $800841$, exact source problem code catalogue entry; supplied complete source record in the AMR Open Problem Lists collection. The record attributes the problem to Bandeira et al., gives proposed year 2025, and labels its status open. This label is supplied curation, not an independently verified mathematical or literature assessment.
• Bandeira et al., Randomstrasse101: Open Problems of 2024 (2025), Problem 6. Supplied source URL: https://arxiv.org/abs/2504.20539. The background records access on 2026-10-16 and extraction method arxiv_latex; these are supplied provenance details, not a claim of access or verification for this draft.