REVIEW 2 major objections 6 minor 58 references
Recovering a group from few orbits
T0 review · 2 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read One generic orbit of an unknown finite unitary group on a complex Hilbert space determines the group up to isomorphism, and two suffice on real Hilbert spaces.
desk verdict Genuinely new one-orbit theorem over C, a plausible two-orbit theorem over R with a fixable proof gap, and an overstated sharpness claim; worth reviewing after revision. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Gram graph of an orbit: the edge-labeled directed graph whose vertices are the orbit's points and whose edge $s \to t$ carries label $\langle s, t \rangle$. For a generic complex orbit this graph is isomorphic to the complete Cayley graph of $G$ (edge $h \to k$ labeled by $h^{-1}k$), which follows from the fact that a generic $x$ makes the level sets of $g \mapsto \langle x, gx \rangle$ coincide with those of $g \mapsto g$ (or $g + g^{-1}$ in the real case). Since every label-preserving automorphism of a complete Cayley graph is left multiplication by a group element, $\operatorname{Aut}(Gv) \cong G$ follows. In real spaces the same graph is too coarse, so the paper pairs two generic orbits and uses the orbit pairing lemma: the map sending each point of the first orbit to its nearest point in the second is a well-defined bijection that is equivariant with respect to every symmetry of the union, transferring the action between orbits and yielding $\operatorname{Aut}(Gv \cup Gw) \cong G$. For concrete recovery the mechanism is representation-theoretic: orbits are viewed as images of equivariant linear maps from $k$ copies of the regular representation, and Schur's lemma translates 'the spans of the orbits have codimension smaller than $r$' into the multiplicity bound $k \ge \max_\pi (n_\pi(V)-(r-1)[\pi=1])/n_\pi(R)$.
What would settle it
Sample a random pair of orbits of the quaternion group $Q_8$ acting by left multiplication on $\mathbb{R}^4$ and count the automorphisms of their union; Theorem 2.12 predicts exactly 8 for every pair in its generic set, so finding a pair with more symmetries, particularly one that preserves distances but is not a single complexified isometry, would disprove the two-orbit theorem.
Extended reading notes
Core claim
The paper establishes that, for a finite group $G$ acting by unitary automorphisms on a finite-dimensional complex Hilbert space $V$, a single generic orbit determines $G$ up to isomorphism: the canonical map $G \to \operatorname{Aut}(Gv)$ is an isomorphism (Theorem 2.6). On a real Hilbert space, two generic orbits suffice, with $G \to \operatorname{Aut}(Gv \cup Gw)$ an isomorphism (Theorem 2.12). For concrete recovery, Corollary 3.5(b) states that if $k \ge [\mathbb{C}:F]$ and $k$ meets the multiplicity bound $k \ge \max_\pi (n_\pi(V)-(r-1)[\pi=1])/n_\pi(R)$, where $r$ is the smallest dimension of a nontrivial representation, then $k$ generic orbits determine $G$ as a subset of $\operatorname{Aut}(V)$; conversely, if $k$ fails that bound, every collection of $k$ orbits can be realized by another subgroup of $\operatorname{Aut}(V)$.
Load-bearing premise
The two-orbit theorem assumes that the two real orbits are permuted in lockstep—that every symmetry of their union also gives a symmetry of the complexified orbit $G(v+iw)$—an assumption supplied by the later orbit pairing lemma but not cited there.
Editorial extensions
If this is right
- In the complex case, an observer who receives one generic orbit can compute the Gram graph and read off the isomorphism class of $G$ without prior knowledge of the dimension or order.
- In the real case, two generic orbits recover the abstract group as $\operatorname{Aut}(Gv \cup Gw)$; one orbit already suffices when $G$ has prime order or $V$ has dimension two.
- The concrete recovery threshold is sharp: if $k$ fails the multiplicity bound, any $k$ orbits can be reinterpreted as orbits of a different subgroup of $\operatorname{Aut}(V)$, while if $k$ meets both the bound and $k \ge [\mathbb{C}:F]$, $k$ generic orbits determine $G$ exactly.
- For $V$ equal to the regular representation over $\mathbb{C}$, a single generic orbit determines the concrete group action; for $G = \{\pm I\}$, genericity lets a single orbit determine the group even though the general bound asks for $d$ orbits.
Reading between the lines
- The Gram graph plus automorphism computation gives a concrete algorithmic route to symmetry discovery from unlabeled point clouds: collect one generic complex orbit, build inner-product labels, and compute the label-preserving automorphism group; the two-orbit theorem supplies the synchronization rule that makes the same pipeline work for real data.
- The orbit pairing lemma's nearest-point bijection is a natural target for numerical experiments: it suggests that approximate orbits can be matched by nearest neighbours before estimating the group, and its equivariance could be checked statistically.
- If the real one-orbit conjecture is true, the distinction between complex and real cases in abstract recovery would vanish entirely, and the second orbit in Theorem 2.12 would be an artifact of the proof rather than an information-theoretic necessity.
- The concrete-recovery bound is a worst-case generic threshold, but Example 3.8 shows genericity itself can carry extra information (such as nonzero centroid), so the number of orbits actually needed in structured families may be far smaller.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the inverse problem of recovering an unknown finite group G of automorphisms (linear isometries) of a finite-dimensional real or complex Hilbert space V from one or more generic G-orbits. In the complex case, it proves (Theorem 2.6) that a single generic orbit determines G up to isomorphism, and that the canonical map G to Aut(Gv) is an isomorphism. In the real case, it proves (Theorem 2.12) that two generic orbits determine G up to isomorphism via the automorphism group of their union. For concrete recovery, Theorem 3.4 and Corollary 3.5 give a representation-theoretic bound on the number of generic orbits needed to determine G as a subset of Aut(V), together with a converse. The paper also provides examples, open problems, and a table of bounds.
Significance. The problem is natural and well motivated by symmetry learning in data science. The complex one-orbit theorem and the representation-theoretic concrete recovery bound are elegant and appear correct; the derivations use generic polynomial arguments and Schur's lemma with no free parameters or fitting. The paper also offers instructive examples showing real-orbit behavior (e.g., Example 2.11) and a counterexample to possible over-strong sharpness (Example 3.8). The main caveat is that the proof of the two-orbit theorem is incomplete as written; however, the gap is local and can be repaired using the paper's own orbit-pairing lemma. If that repair is made, the results constitute a solid contribution.
major comments (2)
- [Section 2, Theorem 2.12 (proof)] The proof defines alpha(sigma)(x+iy)=sigma(x)+i sigma(y) and argues that because sigma extends to a linear isometry M, alpha(sigma) extends to the linear isometry x+iy maps to Mx+iMy and hence belongs to Aut(G(v+iw)). This only shows alpha(sigma) is a linear isometry of the complexification; it does not show that alpha(sigma) maps the finite set G(v+iw) into itself, as required by the definition of Aut. One needs synchronization: for each g in G, the same group element h_g must satisfy sigma(gv)=h_g gv and sigma(gw)=h_g gw. This synchronization follows from Lemma 3.1 because beta(gv)=gw and sigma(gw)=beta sigma(gv), but Lemma 3.1 is neither stated nor cited before Theorem 2.12. The proof should be reorganized to use Lemma 3.1 (or to prove the synchronization directly) before constructing alpha; with that addition the remainder of the argument is valid.
- [Section 3, Corollary 3.5(a)] The proof is only a sketch. The sentence 'we cannot determine whether G acts trivially on the orthogonal complement' does not verify the claim that every combination of k orbits can be realized as orbits of another subgroup. A construction is needed: for arbitrary v_1,...,v_k put S=span(union_i Gv_i); since k fails (1), Theorem 3.4 gives codim S >= r >= 1. Choose a nonzero u in S^perp and let R be the orthogonal reflection in the line through u (fixing u^perp). Then H={g direct sum r : g in G, r in <R>} is a proper subgroup of Aut(V) different from G, and H v_i = G v_i for all i. Inserting this construction would make the lower bound rigorous.
minor comments (6)
- [Section 2, Theorem 2.12] The displayed equation in the injectivity argument contains a typo: the equality should involve alpha(sigma)(g(v+iw)) = sigma(gv) + i sigma(gw), not alpha(sigma)(v+iw) on the right-hand side.
- [Section 3, Lemma 3.1] The chain proving beta sigma = sigma beta for arbitrary sigma implicitly assumes sigma^{-1}(Gw)=Gw, which is established only later in the proof via the norm inequality ||v|| != ||w||. The proof should establish the norm inequality first, or explicitly note that for the G-equivariance step the chain is applied only to sigma in G.
- [Abstract and Table 1] The phrase 'sharp bounds' overstates the real abstract-recovery case: the paper proves an upper bound of 2 and leaves Conjecture 2.7 (one orbit suffices) open. Consider saying 'we give sharp bounds in the complex case and bounds in the real case.'
- [Theorem 2.6(a)] The assertion that the label-preserving automorphism group of the complete Cayley graph is isomorphic to G is stated without proof; a one-line verification (phi(h)=phi(1)h follows from label preservation on edges from 1 to h) would make the proof self-contained.
- [Section 1.2] In the definition of Aut(S), the permutation is first called pi and then sigma in 'M|S=sigma'; the notation should be unified.
- [Example 3.8] The wording 'Corollary 3.5 reports that k orbits determine G as a concrete group only if k>=d' is slightly imprecise because Corollary 3.5(b) is a sufficient condition and part (a) concerns arbitrary combinations; the genericity caveat in the following sentence is important and should be integrated into the phrasing.
Circularity Check
No circularity: group recovery is derived from generic Gram-graph and representation-theoretic arguments; self-citations are background only.
full rationale
I walked the claimed derivation chain. The central recovery results are constructive and do not assume what they prove. Theorem 2.5 proves, by a generic-polynomial argument, that the Gram graph of a generic complex orbit is isomorphic to the complete Cayley graph of G; Theorem 2.6 then recovers the isomorphism class of G from that graph, using the standard fact that label-preserving automorphisms of the complete Cayley graph are left multiplications. No fitted parameter is involved. The real two-orbit theorem (Theorem 2.12) reduces to the complex one-orbit theorem on the complexification V_C; its proof contains a genuine gap, since showing that alpha(sigma) extends to an isometry does not by itself show that it permutes G(v+iw) unless the two real orbits are permuted in a synchronized way. This is an omitted-support problem, not a circular one: the synchronization is supplied later by Lemma 3.1, which is proved independently by an equivariant nearest-point argument, and no step of the theorem uses its own conclusion as a premise. The concrete-recovery results in Section 3 are likewise first-principles: the equivalence in Theorem 3.4 is a generic-polynomial/representation-theoretic criterion, Corollary 3.5 combines it with the multi-orbit theorem, and Schur's lemma is external to the paper's conclusions. Self-citations (e.g., [17], [18], [23], [34], [40], [41]) appear only in related-work or as background and are not load-bearing. Example 3.8 even exhibits a case where the paper's own sufficient bound is larger than necessary, which is the opposite of a conclusion forced by the analysis. No circular step can be exhibited with the required specificity, so the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Standard facts about finite group representations over R and C: semisimplicity, Schur's lemma, multiplicities in regular representation.
- standard math The complement of the zero set of a nonzero polynomial is open and dense in the Zariski topology.
- domain assumption The isomorphism class of the complete Cayley graph / Cayley table of a finite group determines the group up to isomorphism (isotopic groups are isomorphic).
- standard math Finite subgroups of O(2) are cyclic or dihedral (Leonardo da Vinci's theorem).
Cite this review
Pith. "Pith review of Recovering a group from few orbits." pith.science (2026). https://pith.science/paper/AZZ5BW5H
@misc{pith2026241117434,
author = {Pith},
title = {Pith review of: Recovering a group from few orbits},
year = {2026},
howpublished = {\url{https://pith.science/paper/AZZ5BW5H}},
note = {Machine review of arXiv:2411.17434}
}
abstract
For an unknown finite group $G$ of automorphisms of a finite-dimensional Hilbert space, we find sharp bounds on the number of generic $G$-orbits needed to recover $G$ up to group isomorphism, as well as the number needed to recover $G$ as a concrete set of automorphisms.
Figures
Reference graph
Works this paper leans on
-
[1]
T. Amir, S. Gortler, I. Avni, R. Ravina, N. Dym, Neural injective functions for multisets, measures and graphs via a finite witness theorem, NeurIPS 36 (2024)
work page 2024
-
[2]
Balan, P
R. Balan, P. Casazza, D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmon. Anal. 20 (2006) 345–356
2006
- [3]
-
[4]
G-Invariant Representations using Coorbits: Injectivity Properties
R. Balan, E. Tsoukanis, G-invariant representations using coorbits: Injectivity properties, arXiv:2310.16365 (2023)
work page Pith review arXiv 2023
-
[5]
Stability of sorting based embeddings
R. Balan, E. Tsoukanis, M. Wellershoff, Stability of sorting based embeddings, arXiv:2410.05446 (2024)
work page Pith review arXiv 2024
-
[6]
A. S. Bandeira, B. Blum-Smith, J. Kileel, J. Niles-Weed, A. Perry, A. S. Wein, Estimation under group actions: recovering orbits from invariants, Appl. Comput. Harmon. Anal. 66 (2023) 236–319
work page 2023
-
[7]
T. Bendory, N. Dym, D. Edidin, A. Suresh, A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM, arXiv:2405.04354 (2024)
arXiv 2024
-
[8]
T. Bendory, N. Dym, D. Edidin, A. Suresh, Phase retrieval with semi-algebraic and ReLU neural network priors, arXiv:2311.08833 (2023)
arXiv 2023
Show all 58 references
-
[9]
Bendory, D
T. Bendory, D. Edidin, The Sample Complexity of Sparse Multireference Alignment and Single- Particle Cryo-Electron Microscopy, SIAM J. Math. Data Sci. 6 (2024) 254–282
2024
-
[10]
Bendory, D
T. Bendory, D. Edidin, O. Mickelin, The beltway problem over orthogonal groups, arXiv:2402.03787 (2024)
2024 arXiv
-
[11]
Blum-Smith, N
B. Blum-Smith, N. Huang, M. Cuturi, S. Villar, Learning functions on symmetric matrices and point clouds via lightweight invariant features, arXiv:2405.08097 (2024)
2024 arXiv
-
[12]
Blum-Smith, S
B. Blum-Smith, S. Villar, Machine Learning and Invariant Theory, Notices Amer. Math. Soc. 70 (2023) 1205–1213. 12
2023
-
[13]
B¨ oker, R
J. B¨ oker, R. Levie, N. Huang, S. Villar, C. Morris, Fine-grained expressivity of graph neural networks, NeurIPS 36 (2024)
2024
-
[14]
Broome, S
H. Broome, S. Waldron, On the construction of highly symmetric tight frames and complex polytopes, Linear Algebra Appl. 439 (2013) 4135–4151
2013
-
[15]
Cahill, A
J. Cahill, A. Contreras, A. Contreras-Hip, Complete set of translation invariant measurements with Lipschitz bounds, Appl. Comput. Harmon. Anal. 49 (2020) 521–539
2020
-
[16]
Cahill, A
J. Cahill, A. Contreras, A. Contreras-Hip, Stable Separation of Orbits for Finite Abelian Group Actions, J. Fourier Anal. Appl. 30 (2024) 12
2024
-
[17]
Cahill, J
J. Cahill, J. W. Iverson, D. G. Mixon, Towards a bilipschitz invariant theory, Appl. Comput. Harmon. Anal. 72 (2024) 101669
2024
-
[18]
Cahill, J
J. Cahill, J. W. Iverson, D. G. Mixon, D. Packer, Group-invariant max filtering, Found. Comput. Math. (2024) 1–38
2024
-
[19]
Cahill, D
J. Cahill, D. G. Mixon, H. Parshall, Lie PCA: Density estimation for symmetric manifolds, Appl. Comput. Harmon. Anal. 65 (2023) 279–295
2023
-
[20]
Chien, S
T.-Y. Chien, S. Waldron, A characterization of projective unitary equivalence of finite frames and applications, SIAM J. Discrete Math. 30 (2016) 976–994
2016
-
[21]
H. Cohn, A. Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007) 99–148
2007
-
[22]
Conca, D
A. Conca, D. Edidin, M. Hering, C. Vinzant, An algebraic characterization of injectivity in phase retrieval, Appl. Comput. Harmon. Anal. 38 (2015) 346–356
2015
-
[23]
C. Cox, E. J. King, D. G. Mixon, H. Parshall, Uniquely optimal codes of low complexity are symmetric, arXiv:2008.12871 (2020)
2020
-
[24]
Derksen, Bi-Lipschitz Quotient embedding for Euclidean Group actions on Data, arXiv:2409.06829 (2024)
H. Derksen, Bi-Lipschitz Quotient embedding for Euclidean Group actions on Data, arXiv:2409.06829 (2024)
2024 arXiv
-
[25]
N. Dym, S. J. Gortler, Low-dimensional invariant embeddings for universal geometric learning, Found. Comput. Math. (2024) 1–41
2024
-
[26]
Edidin, J
D. Edidin, J. Katz, Generic orbit recovery from invariants of very low degree, arXiv:2408.09599 (2024)
2024
-
[27]
Edidin, M
D. Edidin, M. Satriano, Orbit recovery for band-limited functions, SIAM J. Appl. Algebra Geometry 8 (2024) 733–755
2024
-
[28]
Ennes, R
H. Ennes, R. Tinarrage, LieDetect: Detection of representation orbits of compact Lie groups from point clouds, arXiv:2309.03086 (2023)
2023
-
[29]
Z. Fan, R. R. Lederman, Y. Sun, T. Wang, S. Xu, Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM, Ann. Stat. 52 (2024) 52–77
2024
-
[30]
Fejes T´ oth, Regular figures, Pergamon, 1964
L. Fejes T´ oth, Regular figures, Pergamon, 1964
1964
-
[31]
Fejes T´ oth, Symmetry induced by economy, Symmetry (1986) 83–91
L. Fejes T´ oth, Symmetry induced by economy, Symmetry (1986) 83–91
1986
-
[32]
Fejes T´ oth,¨Uber die dichteste Kugellagerung, Math
L. Fejes T´ oth,¨Uber die dichteste Kugellagerung, Math. Z. 48 (1940) 676–684
1940
-
[33]
Fickus, E
M. Fickus, E. Gomez-Leos, J. W. Iverson, Radon-Hurwitz Grassmannian codes, arXiv:2404.06417 (2024)
2024 arXiv
-
[34]
Fickus, J
M. Fickus, J. W. Iverson, J. Jasper, D. G. Mixon, Equi-isoclinic subspaces from symmetry, arXiv:2406.19542 (2024). 13
2024
-
[35]
I. Hadi, T. Bendory, N. Sharon, SE p3q Synchronization by eigenvectors of dual quaternion matrices, Inform. Inference 13 (2024) iaae014
2024
-
[36]
Hordan, T
S. Hordan, T. Amir, N. Dym, Weisfeiler Leman for Euclidean Equivariant Machine Learning, arXiv:2402.02484 (2024)
2024 arXiv
-
[37]
Hoskins, Y
J. Hoskins, Y. Khoo, O. Mickelin, A. Singer, Y. Wang, Subspace method of moments for ab initio 3-D single-particle Cryo-EM reconstruction, arXiv:2410.06889 (2024)
2024
-
[38]
Huang, R
N. Huang, R. Levie, S. Villar, Approximately equivariant graph networks, NeurIPS 36 (2024)
2024
-
[39]
J. W. Iverson, J. Jasper, D. G. Mixon, More on the optimal arrangement of 2 d lines in Cd, arXiv:2410.17379 (2024)
2024 arXiv
-
[40]
J. W. Iverson, D. G. Mixon, Doubly transitive lines I: Higman pairs and roux, J. Combin. Theory A 185 (2022) 105540
2022
-
[41]
J. W. Iverson, D. G. Mixon, Doubly transitive lines II: Almost simple symmetries, Alg. Combin. 7 (2024) 37–76
2024
-
[42]
E. J. King, D. G. Mixon, S. Waldron, Testing isomorphism between tuples of subspaces, arXiv:2105.03448 (2021)
2021
-
[43]
G. S. Kopp, SIC-POVMs and the Stark conjectures, Int. Math. Res. Not. (2018) rnz153
2018
-
[44]
D. G. Mixon, D. Packer, Max filtering with reflection groups, Adv. Comput. Math. 49 (2023) 82
2023
-
[45]
D. G. Mixon, Y. Qaddura, Injectivity, stability, and positive definiteness of max filtering, arXiv:2212.11156 (2022)
2022 arXiv
-
[46]
D. G. Mixon, Y. Qaddura, Stable Coorbit Embeddings of Orbifold Quotients, arXiv:2403.14042 (2024)
2024
-
[47]
Y. Rong, Y. Wang, Z. Xu, Almost everywhere injectivity conditions for the matrix recovery problem, Appl. Comput. Harmon. Anal. 50 (2021) 386–400
2021
-
[48]
Sverdlov, Y
T. Sverdlov, Y. Davidson, N. Dym, T. Amir, FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network, arXiv:2410.09118 (2024)
2024
-
[49]
Sverdlov, I
Y. Sverdlov, I. Springer, N. Dym, Revisiting Multi-Permutation Equivariance through the Lens of Irreducible Representations, arXiv:2410.06665 (2024)
2024 arXiv
-
[50]
R. Vale, S. Waldron, The symmetry group of a finite frame, Linear Algebra Appl. 433 (2010) 248–262
2010
-
[51]
R. Vale, S. Waldron, Tight frames and their symmetries, Constr. Approx. 21 (2004) 83–112
2004
-
[52]
Villar, D
S. Villar, D. W. Hogg, K. Storey-Fisher, W. Yao, B. Blum-Smith, Scalars are universal: Equivariant machine learning, structured like classical physics, NeurIPS 34 (2021) 28848–28863
2021
-
[53]
Villar, W
S. Villar, W. Yao, D. W. Hogg, B. Blum-Smith, B. Dumitrascu, Dimensionless machine learning: Imposing exact units equivariance, J. Mach. Learn. Res. 24 (2023) 1–32
2023
-
[54]
S. F. D. Waldron, An introduction to finite tight frames, Birkh¨ auser, 2018
2018
-
[55]
Y. Wang, Z. Xu, Generalized phase retrieval: Measurement number, matrix recovery and beyond, Appl. Comput. Harmon. Anal. 47 (2019) 423–446
2019
-
[56]
Weyl, Symmetry, Princeton U
H. Weyl, Symmetry, Princeton U. Press, 1952
1952
-
[57]
L. Yin, A. Little, M. Hirn, Bispectrum Unbiasing for Dilation-Invariant Multi-reference Alignment, arXiv:2402.14276 (2024)
2024 arXiv
-
[58]
Zhang, O
A. Zhang, O. Mickelin, J. Kileel, E. J. Verbeke, N. F. Marshall, M. A. Gilles, A. Singer, Moment-based metrics for molecules computable from cryogenic electron microscopy images, Biol. Imag. 4 (2024) e3. 14
2024
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.