🔢 mathematics

Constructing linear codes from digraphs and groups

This paper introduces two generalizations of Cayley codes called graph and digraph codes, analyzes their algebraic and combinatorial properties to demonstrate improved expansion-based parameter relationships, and constructs an infinite family of good digraph codes.

Original authors: Coen del Valle, Cheryl E. Praeger

Published 2026-07-31

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Coen del Valle, Cheryl E. Praeger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy room. If you just whisper the words, static might garble them. But if you repeat the message in a clever pattern, the listener can figure out the original words even if some parts get lost. This is the magic of error-correcting codes, the mathematical recipes that keep your texts, photos, and bank transfers safe from glitches. For decades, mathematicians have been hunting for the "Goldilocks" code: one that is short enough to send quickly, strong enough to fix many errors, and simple enough for computers to check instantly.

To build these codes, scientists often use two powerful tools: groups (which are like rulebooks for symmetry, telling you how to shuffle things around without breaking the pattern) and graphs (which are just maps of dots connected by lines). A famous type of map is called a Cayley graph, which is built by following a specific set of rules from a group. In 2012, researchers discovered that using these special maps could create a new kind of super-efficient code. But there was a catch: these maps were built from very rigid rules, limiting the kinds of codes you could make. It was like having a fantastic recipe, but you were only allowed to use ingredients from one specific brand.

Now, two mathematicians, Coen Del Valle and Cheryl E. Praeger, have opened the pantry. They have figured out how to build these powerful codes using any kind of map, not just the rigid ones. They call their new creations graph codes and digraph codes. Think of a standard graph as a map where roads go both ways, and a digraph (directed graph) as a map with one-way streets. By using these more flexible maps, the authors show we can create a much wider variety of error-correcting codes. They proved that these new codes are just as strong and efficient as the old ones, but with the added freedom to be built from almost any symmetrical structure you can imagine. This is a big deal because it gives engineers and scientists a whole new toolbox to design better, faster, and more reliable communication systems.

The New Blueprint: From Rigid Rules to Flexible Maps

The paper begins by acknowledging a breakthrough from 2012 by Kaufman and Lubotzky. They were the first to build a family of "symmetric LDPC good codes." Let's break that down: "LDPC" means the code is easy to check (low-density parity-check), "good" means it's both efficient and strong, and "symmetric" means the code looks the same no matter how you rotate or shuffle its parts. They built this using Cayley codes, which are like building a house where every room is a perfect copy of the next, arranged according to a strict group of rules.

Del Valle and Praeger asked a simple question: Do we really need those strict rules? They realized that the magic of Cayley codes didn't come from the group rules themselves, but from the fact that the maps (graphs) they used were vertex-transitive. In plain English, this means the map looks the same from every dot's perspective. If you stand on any dot, the pattern of roads around you looks identical to the pattern around any other dot.

The authors realized that if a map has this "look-alike" property, you don't need it to be a Cayley graph to build a great code. This led to their two main inventions:

Graph Codes: These are built on undirected maps (roads go both ways). You pick a starting dot, look at its neighbors, and apply a small, local code to the connections. Then, because the whole map looks the same from every dot, you copy this local rule everywhere.
Digraph Codes: These are built on directed maps (one-way streets). Here, you have to be a bit more careful because the "out" neighbors (where the road goes) might be different from the "in" neighbors (where the road comes from). So, you apply one local code to the outgoing roads and a different one to the incoming roads.

The Rules of the Game

The authors didn't just invent these codes; they proved they work. They showed that if you choose your local "ingredients" (the small codes) correctly, the final giant code will inherit the symmetry of the map.

They proved a key theorem: If the small code you use on the neighbors respects the symmetry of the map, then the big code will respect the symmetry of the whole map. This is crucial because it means the code is symmetric, which is a desirable trait for making it easy to decode. They also showed that if the small code is "single-orbit symmetric" (a fancy way of saying it's generated by one pattern that repeats), the big code's "dual" (a related code used for checking errors) is also generated by a simple repeating pattern. This makes the new codes highly symmetric and LDPC, meaning they are efficient and easy to check, just like the famous 2012 codes.

One of the most interesting findings is about connectivity. The authors proved that if your map is disconnected (like a map with two separate islands that don't touch), the big code is just a collection of smaller codes built on each island. This means you can focus your attention on building codes for connected maps (one big island), and you'll automatically know how to handle the rest. This simplifies the problem significantly.

The Numbers Game: How Good Are They?

The authors didn't stop at theory; they calculated how good these codes actually are. They looked at two main stats:

Rate: How much useful information you can send compared to the total size of the message.
Relative Distance: How many errors the code can fix.

They found that the new codes perform just as well as the old Cayley codes, and in some cases, even better. Specifically, they improved the mathematical formula used to predict the "error-fighting" power of the code. While the old formula gave a certain lower limit, their new formula pushes that limit slightly higher.

To prove this works in the real world, they constructed an infinite family of these new codes. They used a specific type of directed graph based on a group called $PSL_2(q)$ (a group of matrices) and a prime number $p = 4093$ . They showed that for an infinite number of prime numbers $q$ , they could build codes with:

A rate of at least $2/(p+1)$ , which is roughly $0.0005$.
A relative distance of at least $0.001$.

Because these numbers stay positive no matter how big the code gets, they call this an "infinite family of good digraph codes." This is a major step forward because it proves you can keep making these codes bigger and bigger without them losing their efficiency.

What's Next? Open Questions

The paper ends with a challenge to the rest of the math community. The authors have built a bridge to a new world of codes, but there are still unexplored territories. They pose three specific questions:

Can we find an infinite family of symmetric codes that are not built from Cayley graphs? (They suspect yes, but haven't proven it yet).
Can we find an infinite family of symmetric codes built from proper digraphs? A "proper digraph" is a map where at least one road is one-way (if you can go from A to B, you can't necessarily go from B to A). This is tricky because most known symmetric maps are two-way.
Can we build a symmetric code where the "out" code and the "in" code are different from each other?

The authors also point out that their method can recreate other known code constructions, like the direct product of codes (combining two codes into one big one). In fact, they showed that the famous Petersen graph (a specific, non-Cayley map with 10 dots) can be used to build a code that is highly symmetric but cannot be built as a Cayley code. This is a concrete example of their theory in action: a code that is better or different than what the old rigid rules could produce.

In summary, Del Valle and Praeger have taken a powerful mathematical tool, loosened its constraints, and shown that it works even better with more freedom. They haven't just found a new code; they've found a new way of thinking about how to build them, opening the door to a vast array of possibilities that were previously locked behind the door of strict group rules.

Technical Summary: Constructing Linear Codes from Digraphs and Groups

Problem Statement
The paper addresses the construction of families of "good" linear codes—specifically those that are Low-Density Parity-Check (LDPC), symmetric, and possess both a rate and relative distance bounded away from zero. While Kaufman and Lubotzky (2012) successfully constructed the first family of symmetric LDPC good codes using Cayley codes (based on Cayley graphs), the authors identify a limitation in the reliance on group actions that are regular (i.e., Cayley graphs). The goal is to generalize this construction to a broader class of vertex-transitive (di)graphs, thereby increasing the "freedom" in code design while maintaining the desirable algebraic and combinatorial properties of Cayley codes.

Methodology
The authors introduce two new constructions for linear codes based on vertex-transitive (di)graphs:

Graph Codes: Defined on undirected graphs $\Gamma = (V, E)$ with a vertex-transitive group of automorphisms $G$ . The construction utilizes a transversal $T$ for the stabilizer $G_\alpha$ of a vertex $\alpha$ , and a linear code $B$ defined on the neighborhood $\Gamma(\alpha)$ . The resulting code $C$ consists of functions on the edges $E$ such that their restriction to the neighborhood of any vertex (mapped via the transversal) lies in $B$ .
Digraph Codes: The directed analogue, defined on a digraph $\Gamma = (V, A)$ with a vertex-transitive group $G$ . This construction requires input codes $B_1$ and $B_2$ defined on the out-neighborhood $\Gamma^+(\alpha)$ and in-neighborhood $\Gamma^-(\alpha)$ , respectively.

The methodology relies heavily on group theory and spectral graph theory. The authors analyze the automorphism groups of the resulting codes to determine symmetry properties. They employ the Alon–Chung Expander Mixing Lemma (adapted for digraphs) to bound the relative distance of the constructed codes based on the spectral expansion properties (specifically the second largest eigenvalue magnitude) of the underlying (di)graph.

Key Contributions and Results

Generalization of Cayley Codes: The paper demonstrates that Cayley codes are a special case of graph codes where the group action is regular. The new constructions allow for non-regular actions, expanding the pool of available graphs for code construction.
Symmetry and Automorphism Groups: Theorem 1.1 and Theorem 3.4 establish conditions under which the constructed code $C$ inherits the symmetry of the input graph. Specifically, if the input code $B$ is compatible with the action of the stabilizer $G_\alpha$ (i.e., $G_\alpha^\Gamma(\alpha) \le \text{Aut}(B)$ ), then the full automorphism group of the graph acts on the code $C$ . This allows for the construction of symmetric and highly symmetric codes.
Decomposition Theorems: The authors prove that if the input graph is disconnected, the resulting code decomposes into a direct sum of codes constructed from the connected components (Theorem 1.3 and Theorem 4.4). Furthermore, codes can be decomposed based on orbital subgraphs (Theorems 4.6 and 4.7), allowing for the construction of codes with specific symmetric direct summands.
Improved Distance Bounds:
- For digraph codes, the authors derive a lower bound on the relative distance $\delta(C)$ involving the input distance $\delta(B)$ and the spectral parameter $\lambda$ of the adjacency matrix (Theorem 5.2).
- For graph codes, they provide a bound (Theorem 5.3) that improves upon the standard result for Cayley codes found in previous literature (specifically [5, Theorem 2]). The bound is given by $\delta(C) \ge \delta(B) \cdot \frac{\delta(B) - (\lambda/v)}{1 - (\lambda/v)}$ .
Rate Bounds: The paper establishes lower bounds on the rate $r(C)$ , showing that for graph codes $r(C) \ge 2r(B) - 1$ and for digraph codes $r(C) \ge r(B_1) + r(B_2) - 1$ (Theorem 5.6).
Applications and Examples:
- The authors show that the construction generalizes the direct (Kronecker) product of codes (Theorems 6.1 and 6.2).
- They construct a specific highly symmetric graph code using the Petersen graph (which is not a Cayley graph) and the length-3 augmentation code, resulting in a $[15, 6, 5]_2$ code that cannot be realized as a Cayley code.
- Using Theorems 5.2 and 5.6, they construct an infinite family of "good" proper digraph codes (codes where the underlying digraph is not symmetric in arcs) with rate $\approx 0.0005$ and relative distance $\approx 0.001$ .

Significance and Claims
The paper claims that these constructions offer "added freedom" compared to the original Cayley code framework. By decoupling the code construction from the requirement of a regular group action, the authors can utilize a wider class of vertex-transitive graphs.

The primary significance lies in the theoretical improvement of the distance bounds for graph-based codes, which translates to a modest but concrete improvement over the results of Kaufman and Lubotzky regarding symmetric LDPC good codes. The authors explicitly state that their analysis of the relationship between expansion properties and code parameters offers an improvement to existing results.

Furthermore, the paper highlights the existence of symmetric LDPC good codes that are not Cayley codes (demonstrated via the Petersen graph example), answering a structural question about the necessity of Cayley graphs for such constructions. The authors conclude by posing open problems regarding the existence of infinite families of symmetric LDPC good codes that are "proper" digraph codes or constructed from non-isomorphic input codes, framing these as the next logical steps in the field.

The New Blueprint: From Rigid Rules to Flexible Maps

The Rules of the Game

The Numbers Game: How Good Are They?

What's Next? Open Questions

More like this