Random non-commutative codes achieve good error correction in certain groups
Random Non-Commutative Error-Correcting Codes
Information Theory
Summary
Error-correcting codes help detect and fix errors in data, usually using math where order doesn’t matter (commutative). This paper studies codes in settings where order matters (non-commutative groups). The authors find that random codes work well only in groups with specific growth properties, like solvable groups, while they perform poorly in free groups. They also provide exact measurements of how well these codes can work depending on the group.
What this means in practice
- •For coding theory engineers: Design error-correcting schemes adapted to data structured by complex group symmetries with guaranteed performance in solvable group contexts.
- •For cryptography developers: Assess feasibility of constructing error-resilient protocols using group-theoretic constructs with predictable error bounds from maximal-subgroup growth properties.
A theory result. No direct application yet.
Authors
Michael Best, Alexander Lubotzky
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.