Irreducible cyclic codes with rare non-standard symmetries have density zero
A density theorem for non-standard irreducible cyclic codes
Information Theory
Summary
Some special types of error-correcting codes, called irreducible cyclic codes, can sometimes have unusual symmetries beyond the usual cyclic shifts and field-related actions. The authors prove that for almost all code lengths relative to a fixed prime number, such unusual symmetries almost never occur. This means that for nearly every length, these codes only have the expected standard symmetries, simplifying their structure and analysis. Their proof combines previous classifications of such codes with results on number theory about multiplicative orders.
What this means in practice
- •For error correction engineers: Determine when irreducible cyclic codes have only standard symmetries, reducing complexity in code analysis and implementation.
- •For cryptographic protocol developers: Use the rarity of non-standard automorphisms in code design to avoid unexpected symmetries that may weaken security assumptions.
A theory result. No direct application yet.
Authors
Tao Feng, Henk D. L. Hollmann, Weicong Li, Qing Xiang
Abstract
We prove a fixed-characteristic density form of the Berger-Charpin conjecture for non-degenerate irreducible cyclic codes: for each prime $p$, the lengths admitting such a non-standard code over some finite field of characteristic $p$ have natural density zero. Thus, for almost every length coprime to $p$, every such code over every finite field of characteristic $p$ has only the permutation automorphisms generated by the cyclic shift and the Frobenius map. The proof uses the Feng--Hollmann--Li--Xiang classification for non-standard irreducible cyclic codes, a normal form for the deriving constructions in that paper, and a theorem by Wiertelak on multiplicative orders, in the form recalled by Moree.