Structure of Cayley Codes
Vishnuram Arumugam, Cheryl E. Praeger, Daniel Rademacher · 2026
Read Structure of Cayley Codes by Vishnuram Arumugam, Cheryl E. Praeger, Daniel Rademacher (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28611.txt.
Introduction
Vishnuram Arumugam, Cheryl E. Praeger, and Daniel Rademacher explore Cayley codes, error-correcting codes built by Kaufman and Wigderson from a Cayley graph of a group together with a smaller code. Their algebraic symmetry makes them attractive, but the general theory of the construction was thin.
The authors prove a reduction: attention can be restricted to codes from connected Cayley graphs without losing rate, minimum distance, or symmetry. For any given Cayley code, they pick out a family of symmetric Cayley codes, each tied to a normal edge-transitive graph. The family's direct sum contains the original, letting symmetric pieces carry the analysis. Several families of examples are worked through, including how the construction behaves under direct and cartesian products of graphs. A list of open questions points at where the theory of these highly symmetric codes goes next.
Catalog record
| CREATOR | Vishnuram Arumugam, Cheryl E. Praeger, Daniel Rademacher |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28611
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structure of Cayley Codes Vishnuram Arumugam, Cheryl E. Praeger, Daniel Rademacher Abstract . Cayley codes, introduced by Kaufman and Wigderson, are linear codes constructed from a Cayley graph and a smaller linear code. We explore general properties of the class of Cayley codes for finite groups. In particular we give a reduction to Cayley codes for connected Cayley graphs that maintains code properties such as rate, minimum distance and symmetry. Also, for a given Cayley code, we identify a family of symmetric Cayley codes, each associated with a normal edge-transitive Cayley graph, such that the given Cayley code embeds into the direct sum of the symmetric Cayley codes. We analyse several families of examples, in particular studying the behaviour of the Cayley code construction under forming direct products and cartesian products of Cayley graphs, and we pose a number of open questions. Key-words: Cayley graph, Cayley code, linear code, graph symmetry 2020 Mathematics Subject Classification: 05B05, 20B25, 05B25 Corresponding author: Cheryl E Praeger 1. Introduction In 2010, Kaufman and Wigderson introduced a new construction of linear codes, which they called Cayley codes, taking as input a Cayley graph and a smaller linear code (see [ 5 ] , or [ 6 , Definition 19] for the journal version). They proved [ 6 , Theorem 7] that, for suitable input graphs and codes, the Cayley code construction preserves certain bounds on the rate or relative distance, and desirable code properties such as being symmetric. They presented explicit families of Cayley codes based on Cayley graphs of elementary abelian 2 -groups [ 6 , Section 4] , obtaining codes of length n which were ‘almost good’ in the sense that the relative distance was O((\log\log n)^{-2}) , rather than being strictly bounded away from zero, see [ 6 , Theorem 11] . Kaufman and Lubotzky [ 3 ] commented in 2012 that ‘ it seems that all the known explicit constructions of symmetric codes give codes which are not good ’, and provided, via the Cayley code construction, the first explicit infinite family of good binary symmetric codes based on the edge-transitive bipartite Ramanujan graphs – particular Cayley graphs for the projective linear groups {\rm PGL}_{2}(q) , [ 7 , 8 ] (see Notation 1.1 for definitions of technical terms such as ‘good’). Becker [ 1 ] explored the impact of the expansion and symmetry properties of Ramanujan graphs on the properties of these Cayley codes; while Kaufman and Oppenheim [ 4 ] developed a higher dimensional version. The aim of this paper is a little different. We explore general properties of the class of Cayley codes for finite groups. We show how to reduce to Cayley codes for connected Cayley graphs while maintaining the same rate and minimum distance and symmetry propertties (Theorem 4.1 ). We identify a family of symmetric Cayley codes related to an arbitrary given Cayley code (Theorem 1.3 ). Normal edge-transitive Cayley graphs introduced in [ 9 ] play a critical role in the second reduction. Finally we give several families of examples, in particular exploring the behaviour of the Cayley code construction under the Cartesian product construction for graphs (Theorem 1.4 ). We give broad statements of the major results in Subsection 1.1 , and to facilitate these statements we introduce the relevant concepts in Notation 1.1 . The final Subsection 7.3 briefly discusses some open questions about the structure of finite Cayley codes. Notation 1.1 . A linear [n,k,d] -code over a finite field \mathbb{F} is a k -dimensional subspace C of \mathbb{F}^{X} , where |X|=n , such that the minimum (Hamming) weight of the non-zero codewords (elements of C ) is d . A family \mathcal{F} of such codes with length n\to\infty is called good if there exists \epsilon>0 such that the rate r(C):=\frac{k}{n} and the relative distance \delta(C):=\frac{d}{n} are both at least \epsilon . The automorphism group {\rm Aut}(C) of a linear code C<\mathbb{F}^{X} is the subgroup of the symmetric group {\rm Sym}(X) that leaves C invariant in its induced action on \mathbb{F}^{X} , and C is called symmetric if {\rm Aut}(C) is transitive on X . We regard \mathbb{F}^{X} as the \mathbb{F} -vector-space of functions f:X\to\mathbb{F} , so that in particular, for a subset Y\subseteq X , the restriction map f\to f|_{Y} defines a natural projection \mathbb{F}^{X}\to\mathbb{F}^{Y} . For a group G and an inverse-closed subset S\subseteq G\setminus\{1\} , the Cayley graph \Gamma={\rm Cay}(G,S)=(G,E) is the graph with vertex-set V\Gamma=G , and edge-set E\Gamma=E:=\{\{g,sg\}\mid g\in G,s\in S\} . For g\in G , the edge-subset (1) E_{g}:=\{\{g,sg\}\mid s\in S\}\quad\text{is the set of edges incident with $g$,} the map (2) \phi_{g}:S\to E_{g}\quad\text{given by}\quad\phi_{g}:s\to\{g,sg\}\quad\text{for $s\in S$} is a bijection, and we obtain a linear projection \phi:\mathbb{F}^{E}\to\mathbb{F}^{S} , where \phi:f\to\phi_{g}\circ f . The Cayley code \mathbf{C}(G,S,B) corresponding to a given Cayley graph {\rm Cay}(G,S) and linear code B\leq\mathbb{F}^{S} , is (3) \mathbf{C}(G,S,B):=\{f\in\mathbb{F}^{E}\mid\forall\ g\in G,\ \phi_{g}\circ f\in B\}. That \mathbf{C}(G,S,B) is a linear code in \mathbb{F}^{E} follows from the fact that B is a linear code in \mathbb{F}^{S} . The automorphism group {\rm Aut}(\mathbf{C}(G,S,B)) contains the group G\rtimes A(G,S,B) , where (4) A(G,S,B)=\{\sigma\in{\rm Aut}(G)\mid S^{\sigma}=S,\sigma^{S}\in{\rm Aut}(B)\} and in particular, if G\rtimes A(G,S,B) is transitive on the edge-set E then {\rm Cay}(G,S) is normal edge-transitive and also \mathbf{C}(G,S,B) is symmetric (Proposition 3.1 - this strengthens a result [ 3 , 5 , 6 ] , see Remark 3.2 ). 1.1. The main results A Cayley graph {\rm Cay}(G,S) is disconnected if and only if the subgroup H:=\langle S\rangle is a proper subgroup of G and the connected component of {\rm Cay}(G,S) containing the identity is {\rm Cay}(H,S) (Lemma 2.2 ). Thus we can form both Cayley codes \mathbf{C}(G,S,B) and \mathbf{C}(H,S,B) , for appropriate B , and our first result shows how they are related. Theorem 1.2 . Let G be a finite group and S a non-empty inverse-closed subset of G\setminus\{1\} such that H:=\langle S\rangle\neq G . Then for each linear code B\leq\mathbb{F}^{S} , (a) the Cayley code \mathbf{C}(G,S,B) decomposes as a direct sum of |G:H| linear codes, each isomorphic to \mathbf{C}(H,S,B) . (b) Moreover, \mathbf{C}(H,S,B) and \mathbf{C}(G,S,B) have the same rate and minimum distance, and \mathbf{C}(H,S,B) is symmetric if and only if \mathbf{C}(G,S,B) is symmetric. This result allows us to restrict to connected Cayley graphs if we wish. It follows immediately from a more technical version Theorem 4.1 which is proved in Section 4 . We next show that each Cayley code determines a family of symmetric Cayley codes. For G,S,B,A(G,S,B) as in Notation 1.1 , the group A(G,S,B) leaves invariant a unique finest partition S=\cup_{i\in\mathbf{I}}S_{i} such that each S_{i} is inverse-closed and A(G,S,B) -invariant, and we have B\leq\mathbb{F}^{S}=\oplus_{i\in\mathbf{I}}\mathbb{F}^{S_{i}} . For each i , let B_{i} be the restriction of B to \mathbb{F}^{S_{i}} . We show that each of the corresponding Cayley codes \mathbf{C}(G,S_{i},B_{i}) is symmetric. Theorem 1.3 . With the notation above, for each i\in\mathbf{I} , the Cayley graph {\rm Cay}(G,S_{i}) is normal edge-transitive and the Cayley code \mathbf{C}(G,S_{i},B_{i}) is symmetric. Further, if B=\oplus_{i\in\mathbf{I}}B_{i} , then \mathbf{C}(G,S,B)=\oplus_{i\in\mathbf{I}}\mathbf{C}(G,S_{i},B_{i}) . This result is proved in Section 5 . Finally we look at various examples of Cayley codes. In Section 6 we consider Cayley codes for several standard choices of the input code B , and for the family