Exact Group Recovery from Subquadratic Observations

Recovering a finite group operation table from partial observations presents a fundamentally unusual completion task. Unlike classical matrix completion, which relies on a low-rank prior and geometric incoherence to interpolate missing entries, completing a group table requires enforcing an associativity prior and exploiting the discrete Latin-square property, which guarantees uniform marginals without structural incoherence assumptions. We resolve this by analyzing a canonical operator-valued factorization model under gradient-sensitivity regularization. This objective forces the model's latent matrix embeddings to become unitary and satisfy the exact multiplication laws of the observed pairs once a basic coverage threshold of $n\log (3n/\delta )$ observations is reached (coupon collector). By identifying the structural observation patterns required to propagate these localized relations into exact global recovery, we establish sub-quadratic sample complexity bounds under two regimes. Under active query selection, a presentation-dependent scaffold deterministically recovers the complete table in at most $3n-2+|R_{\mathrm{indep}}|$ queries, where $|R_{\mathrm{indep}}|$ counts the pairs needed to close the relator cycles, by tracing a Cayley spanning tree and the group's defining relators to algebraically synchronize the representations. Under passive Bernoulli sampling, $\mathcal{O}(n^{3/2}\sqrt{\log n})$ expected observations guarantee exact table recovery with high probability, as overlapping observations form connected graphs that globally propagate the associativity prior. In both regimes, evaluating all negative candidate outputs for just one observed input pair provides the necessary anchor to eliminate degenerate solutions and select the regular representation. These bounds establish the first closed theory of partial-observation learning for general finite groups, verified formally in Lean 4 and empirically across 32 group families.