Random Non-Commutative Error-Correcting Codes
math.GR, cs.IT, math.IT
Submitted: 2026-10-28
Updated: 2026-10-28
Comments: 18 pages, 1 table
License: http://creativecommons.org/licenses/by/4.0/
The gist: Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes…
Abstract
Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via δ-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.
Related papers
- Idempotence criteria for lazy cellular automata
- From algebraic orthogonality to RAAG embedding obstructions in hierarchically hyperbolic groups
- A finitely generated Linear group without property (T) that is neither inner amenable nor properly proximal
- From almost tight p-group enumeration to 2-group domination among finite groups
- Character Nonvanishing under Coprime Actions
- Dyer groups have the falsification by fellow-traveller property