Random 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
- Four New Single-Error-Correcting Binary Codes
- Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
- The Exact Second Generalized Covering Radius of Binary Primitive Triple-Error-Correcting BCH Codes
- RPA Decoding with Few Subspace Projections for Correcting Structured Error Patterns in RM Codes
- Improved bounds for constant-power and low-power error-correcting cooling codes
BibTeX
@misc{best2026random,
title = {{Random Non-Commutative Error-Correcting Codes}},
author = {Michael Best and Alexander Lubotzky},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38804},
eprint = {2610.38804},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38804},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random Non-Commutative Error-Correcting Codes
AU - Michael Best
AU - Alexander Lubotzky
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38804
UR - https://arxiv.org/abs/2610.38804
AB - 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.
ER -