🔢 mathematics

$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

This paper introduces a new explicit infinite family of 2-quasi-perfect $p$ -ary Lee codes derived from cubic generating sets in finite fields and establishes a unified theoretical framework connecting these codes to abelian Ramanujan graphs, specifically Li's and finite Euclidean graphs.

Original authors: Shohei Satake

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shohei Satake

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 a postmaster in a futuristic city where mail is delivered not by streets, but by a grid of numbers. In this city, the "distance" between two addresses isn't just how many blocks you walk; it's a special rule called Lee Distance. If you live at house #1 and your friend lives at house #100, and the city wraps around like a circle, the distance might be small because you can just walk the other way.

Now, imagine you want to send a message that might get slightly scrambled (like a typo). You need a system of "safe houses" (codes) where, even if the message gets a little bit of noise, you can still figure out exactly which safe house it was meant for.

This paper is about building the perfect (or nearly perfect) map of these safe houses.

The Big Problem: The "Perfect" Map is Hard to Find

For a long time, mathematicians have been trying to find a map where every single point in the city is exactly the right distance from a safe house. This is called a Perfect Code. It's like a puzzle where every single piece fits perfectly with no gaps and no overlaps.

However, a famous guess (the Golomb-Welch conjecture) says that for most complex cities, these "perfect" maps simply don't exist. It's like trying to tile a floor with a weirdly shaped tile that just won't fit everywhere without leaving gaps.

So, mathematicians settled for "Quasi-Perfect" codes. These are maps that are almost perfect. They might have a tiny bit of overlap or a tiny gap, but they are the best we can do. The author of this paper, Shohei Satake, is trying to find new, better ways to build these "almost perfect" maps for very large cities.

The New Construction: A Cubic Curve Recipe

Satake introduces a brand new recipe for building these maps.

The Old Way: Previous methods were like using a specific, rigid blueprint. They worked, but they felt a bit isolated and didn't explain why they worked so well.
The New Way: Satake uses a shape called a cubic curve (specifically, the equation $y = x^3$ ) in a mathematical playground called a "finite field."

The Analogy:
Imagine you have a giant, magical dice (the finite field). You roll it, and for every number you get, you plot a point on a graph where the height is the cube of the number.

Satake says: "If you take all these points and use them as the 'generators' (the rules) for your map, you get a 2-quasi-perfect code."
This means the map covers the city efficiently, ensuring that even if a message is slightly off, it's still close enough to a safe house to be corrected.

The Secret Ingredient: Ramanujan Graphs

Here is where the paper gets really cool. Satake connects these codes to something called Ramanujan Graphs.

What is a Ramanujan Graph?
Think of a graph as a network of friends. A "Ramanujan Graph" is a super-efficient network.

High Connectivity: Everyone is connected to everyone else very quickly.
Pseudo-Randomness: Even though the network is built with strict rules, it looks and behaves like a completely random mess of connections. It's the "Goldilocks" of networks: not too ordered, not too chaotic, but just right.

The Connection:
Satake discovered that the new codes he built are actually the same thing as these super-efficient networks.

The "Diameter" Trick: In a network, the "diameter" is the longest distance you have to travel to get from one person to another. Ramanujan graphs have very small diameters.
Why it matters: In our code map, a small diameter means you can't get very far from a "safe house" without hitting one. This is exactly what you need for a code to be "quasi-perfect."

Bridging the Gap

Before this paper, there were two different groups of mathematicians:

The Code Builders: People making these error-correcting maps (like Mesnager, Tang, and Qi).
The Graph Theorists: People studying these super-efficient networks (like Li's graphs and Euclidean graphs).

They were working in separate rooms, not realizing they were building the same thing. Satake's paper is like opening a door between the two rooms. He shows that:

The codes built by Mesnager, Tang, and Qi are actually just different views of these famous Ramanujan graphs.
His new code (based on the $y=x^3$ curve) is a new type of Ramanujan graph that no one had noticed before.

Why Should You Care?

Better Communication: These codes help us send data (like images, videos, or space signals) without errors. If we can build better codes, our internet and space missions become more reliable.
Mathematical Unity: The paper shows that two seemingly different areas of math (coding theory and graph theory) are actually two sides of the same coin. It's like realizing that a recipe for bread and a recipe for cheese are actually using the same secret ingredient.
The "Random vs. Ordered" Paradox: The paper points out a fascinating mystery. These graphs look random (which is good for spreading information), but they have a very strict, ordered structure (which is required to fix errors). It's like a jazz band that sounds improvised but is actually following a very strict, hidden sheet music.

In a Nutshell

Shohei Satake found a new, simple way to build "error-correcting maps" for digital communication. He did this by using a specific mathematical curve ( $y=x^3$ ) and realized that these maps are actually the same thing as "super-efficient networks" known as Ramanujan graphs. This discovery not only gives us new tools for better data transmission but also unifies two different branches of mathematics, showing that the best codes and the best networks are built on the same beautiful, hidden principles.

1. Problem Statement

The paper addresses the construction of 2-quasi-perfect Lee codes over finite fields.

Context: A Lee code is an error-correcting code using the Lee distance. A code is t-perfect if it corrects $t$ errors and covers the entire space with radius $t$ . A code is t-quasi-perfect if it corrects $t$ errors but requires a covering radius of $t+1$ .
The Challenge: Finding perfect Lee codes is a classical problem (constrained by the Golomb-Welch conjecture), but constructing explicit families of quasi-perfect codes, especially for arbitrarily large lengths, remains a significant open problem.
The Gap: Existing constructions (e.g., by Camarero-Martínez and Mesnager-Tang-Qi) often appear as isolated families derived from specific polynomials. There is a lack of a unified theoretical framework explaining why certain algebraic structures yield these optimal codes and how they relate to Abelian Ramanujan graphs (graphs with optimal spectral gaps).

2. Methodology

The author employs a synthesis of coding theory, algebraic geometry, and spectral graph theory.

A. Generic Construction Framework

The paper utilizes the generic construction by Mesnager, Tang, and Qi, which defines a linear code $C(\Gamma, H)$ based on a vector space $\Gamma$ and a generating set $H$ .

Condition for 2-Quasi-Perfectness: The code is 2-quasi-perfect if and only if:
1. The size of the union of sumsets $\bigcup_{i=0}^2 H^{(i)}$ equals $2n^2 + 2n + 1$ (where $n$ is the code length).
2. The union $\bigcup_{i=0}^3 H^{(i)}$ spans the entire space $\Gamma$ .
3. Specific bounds on the size of $\Gamma$ are met.
Graph Connection: These conditions imply that the Cayley graph $Cay(\Gamma, H)$ has a diameter of 3. The author posits that selecting $H$ such that $Cay(\Gamma, H)$ is an Abelian Ramanujan graph (minimizing the spectral gap) is a promising strategy, as these graphs inherently possess small diameters.

B. New Explicit Construction (Theorem 4)

The author introduces a new infinite family of codes derived from the finite field $\mathbb{F}_{q^2}$ (where $q = p^k, p \ge 5$ ).

Generating Set: $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ . This set represents points on the cubic curve $y = x^3$ .
Proof Strategy: The proof relies on verifying the conditions of the generic framework using algebraic geometry:
- Counting Points: Using combinatorial arguments to count solutions to $a = x+y$ and $b = x^3+y^3$ (Lemma 11).
- Irreducibility: Proving that the polynomial $F_{a,b}(x,y) = xy(x+y) - a(x+y)^2 + a^2(x+y) + \frac{b-a^3}{3}$ is absolutely irreducible unless $b=a^3$ (Lemma 12).
- Existence of Solutions: Applying the Hasse-Weil bound to the cubic curve $C_{a,b}$ to ensure that for $q \ge 14$ , there exist non-zero solutions $x, y, z$ such that $a = x+y+z$ and $b = x^3+y^3+z^3$ (Lemma 13). This confirms the diameter condition.

C. Unification of Existing Constructions

The paper analyzes the codes constructed by Mesnager, Tang, and Qi (MTQ) and connects them to known Ramanujan graphs:

Li's Graphs: The MTQ codes for specific parameters correspond to Li's graphs (Cayley graphs over $\mathbb{F}_{q^2}$ generated by the norm-1 elements).
Finite Euclidean Graphs: The MTQ codes are shown to be instances of Finite Euclidean graphs (Cayley graphs generated by quadratic forms $Q(x,y)=1$ ).
Equivalence: The author proves that any code derived from a non-degenerate quadratic form is equivalent (up to coordinate permutation and sign changes) to one of the two standard MTQ families.

3. Key Contributions

New Infinite Family of Codes:
- Constructed a new explicit family of 2-quasi-perfect $p$ -ary Lee codes with length $n = \frac{q-1}{2}$ and dimension $k = \frac{q-1}{2} - 2k$ (where $q=p^k \ge 14$ ).
- These codes are derived from the set $H_q = \{(a, a^3)\}$ , which is distinct from the generating sets used in previous MTQ constructions.
- Novelty: These codes provide new parameters for primes $p \equiv 1, 7 \pmod{12}$ , where previous constructions were limited or non-existent.
Theoretical Unification:
- Established a bridge between Lee codes and Abelian Ramanujan graphs.
- Demonstrated that the MTQ codes are essentially derived from Li's graphs and Finite Euclidean graphs, both of which are known to be Ramanujan.
- Provided a unified description showing that the MTQ construction covers all codes generated by non-degenerate quadratic forms.
Structural Insights:
- Showed that the new codes (based on $y=x^3$ ) are not isomorphic to the Cayley graphs associated with known MTQ codes, despite sharing similar parameters in some cases.
- Highlighted that the new construction stems from recent work on almost Ramanujan graphs by Forey et al. [7].

4. Results

Theorem 4: Proves that for $p \ge 5$ and $q = p^k \ge 14$ , the code $C(\mathbb{F}_q^2, H_q)$ is a 2-quasi-perfect Lee code with length $\frac{q-1}{2}$ and dimension $\frac{q-1}{2} - 2k$ .
Proposition 16 & 18: Proved that the MTQ codes coincide with codes generated by Li's graphs and Finite Euclidean graphs, unifying the theory of these codes under the umbrella of quadratic forms and Ramanujan graphs.
Examples: Provided explicit parity-check matrices for small primes ( $p=17, 19, 23, 5$ ) to illustrate the distinct algebraic structures of the new codes compared to MTQ codes.

5. Significance

Bridging Disciplines: The paper successfully integrates coding theory with spectral graph theory, suggesting that the "good" properties of quasi-perfect codes (small covering radius) are intrinsically linked to the spectral properties of Ramanujan graphs (optimal expansion).
Solving an Open Problem: It contributes to the difficult problem of constructing quasi-perfect codes of arbitrarily large length, offering a new, simple, and explicit construction.
Spectral vs. Structural Dichotomy: The concluding remarks highlight a fascinating theoretical insight: while Ramanujan graphs are spectrally indistinguishable from random graphs (pseudo-random), the strict structural conditions required for 2-quasi-perfectness (deterministic local structure) are rare even in such graphs. This suggests that finding such codes requires more than just spectral optimality; it requires specific algebraic alignments.
Future Directions: The work opens the door to investigating other Abelian Ramanujan graphs to discover further families of optimal codes, solidifying the connection between the Lee distance metric and graph spectra.