🔢 mathematics

The multilinear forms Cayley graph and the eigenvalue method for tensor codes

This paper generalizes the connection between coding theory and graph theory to tensor spaces by analyzing the spectrum of the Cayley graph generated by rank-one tensors, deriving a recursive expression for its eigenvalues based on intersections with the Segre variety, and applying these results to establish new dimension bounds for tensor codes using the eigenvalue method.

Original authors: Eimear Byrne, Lucien François

Published 2026-07-31

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Eimear Byrne, Lucien François

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 channel, like a walkie-talkie that sometimes garbles your words. In the world of mathematics and computer science, this is the job of coding theory: designing messages that are so special that even if a few letters get scrambled, the receiver can still figure out what you meant. To do this, mathematicians treat every possible message as a point in a giant, multi-dimensional city. The "distance" between two points tells you how different the messages are. If two messages are far apart, a little bit of noise won't accidentally turn one into the other.

For decades, scientists have used a powerful tool called graph theory to map out these cities. Think of a graph as a web of dots (messages) connected by lines (if the messages are "close" to each other). By studying the shape of this web, mathematicians can figure out the absolute maximum number of messages you can pack into the city without them getting too close and causing confusion. This works beautifully for simple, flat messages (like text) or even 2D grids (like images). But what happens when your messages are 3D cubes, or even higher-dimensional blocks? These are called tensors. They are the building blocks of complex data, like 3D video or advanced AI models. The problem is, these 3D shapes are messy. The rules that worked for flat grids break down when you add a third dimension, and the "distance" between these shapes becomes incredibly hard to calculate. Until now, no one had a complete map of the connections between these 3D shapes, leaving a huge gap in our ability to design perfect codes for them.

This paper takes a giant step forward by building a new kind of map for these 3D (and higher) shapes. The authors, Eimear Byrne and Lucien François, treat the space of all possible tensors as a giant playground where every point is a tensor. They connect two points with a line if they are "neighbors"—meaning you can turn one into the other by changing just a single, tiny building block. This creates a massive, intricate web called a Cayley graph.

The big discovery here is that while this web is too messy to be a perfect, orderly grid (mathematicians call this "not distance-regular"), it still has a hidden, rhythmic pattern. The authors figured out how to calculate the spectrum of this graph. In simple terms, the spectrum is like the "musical notes" the graph hums when you pluck it. These notes (called eigenvalues) reveal the graph's hidden structure. The authors found a clever, recursive way to calculate these notes. Instead of trying to solve the whole 3D puzzle at once, they showed you can figure out the notes for a 3D shape by looking at the notes of its 2D "slices" (like looking at the layers of a cake).

Using this recipe, they managed to write down the exact musical notes for a specific, tricky type of 3D block: a 2 × 3 × 3 tensor over any finite field. This is a huge deal because, for these shapes, the old rules of thumb didn't work. By knowing the exact notes, they could apply a mathematical technique called the eigenvalue method to set new, stricter limits on how many messages you can send without errors.

The paper proves that for these specific 3D codes, the old "best guess" limits (called Singleton-like bounds) were too optimistic for codes with small minimum distances. However, the authors clarify that for codes with large minimum distances, the previously known "improved Singleton bounds" actually remain the sharpest limits. The new limits derived from the graph's spectrum are tighter specifically for the small-distance cases, meaning we now know for sure that you cannot pack as many messages into these 3D spaces as we previously thought was possible in those scenarios. For example, for a code with a minimum distance of 3 in a 2×3×3 space over a field of size 2, the old limit suggested you could have a code of size 16, but the new math proves you can't even reach 12. The authors didn't just guess this; they calculated the exact spectrum and used it to derive these bounds mathematically. They also provided computer code so others can do the same math for other shapes.

In short, this paper doesn't just solve a puzzle; it builds a new ruler for measuring the limits of 3D data. It shows that the "music" of these complex shapes is more complex than we thought, and by listening closely to that music, we can finally stop overestimating how much information we can safely store in 3D space, particularly when the messages need to be very close to each other.

Technical Summary: The Multilinear Forms Cayley Graph and the Eigenvalue Method for Tensor Codes

Problem Statement
The paper addresses the "main coding theory problem" for tensor codes of order $m \ge 3$ : determining the maximum cardinality of a code with a fixed minimum tensor rank distance. While the framework for Hamming-metric and rank-metric codes is well-established through Delsarte's theory of association schemes and distance-regular graphs, this approach fails for higher-order tensors. Specifically, the ambient space of $m$ -order tensors, endowed with the tensor rank metric, corresponds to a Cayley graph generated by rank-one tensors (the Segre variety). For $m \ge 3$ , this graph is not distance-regular, rendering Delsarte's linear programming bounds inapplicable. The authors seek to overcome this limitation by applying the eigenvalue method to derive upper bounds on the size of tensor codes without relying on distance-regularity.

Methodology
The authors model the space of $m$ -order tensors over a finite field $\mathbb{F}_q$ , denoted $\mathbb{F}_q^n$ , as the vertex set of a Cayley graph $\Gamma = \text{Cay}(\mathbb{F}_q^n, S_n)$ , where $S_n$ is the set of rank-one (simple) tensors. Two vertices are connected if their rank distance is 1. The geodesic distance in this graph coincides with the tensor rank distance.

The core methodology involves computing the spectrum (eigenvalues and multiplicities) of this graph using character theory of finite abelian groups. The key steps include:

Recursive Eigenvalue Formulation: The authors derive an iterative formula (Theorem 34) expressing the eigenvalue $\lambda_x$ associated with a tensor $x$ in terms of the eigenvalues of the slice spaces of $x$ . This reduces the problem of computing eigenvalues for $m$ -order tensors to those of $(m-1)$ -order tensors.
Dual Expression: A dual formula (Theorem 42) is established, linking the eigenvalue $\lambda_x$ directly to the number of rank-one tensors in the dual of a slice space of $x$ . This connects the graph spectrum to the intersection cardinalities between subspaces and the Segre variety.
Classification-Based Computation: For the specific case of $2 \times 3 \times 3$ tensors, the authors utilize the known classification of subspaces of $\mathbb{F}_q^{2 \times 3}$ and tensor orbits under the general linear group action (Lavrauw and Sheekey). This allows for the explicit calculation of the full spectrum, including multiplicities, by enumerating orbit sizes and rank distributions.
Application of Eigenvalue Bounds: Once the spectrum is determined, the authors apply the ratio-type and inertia-type bounds (Theorems 16 and 17) to the independence numbers of the graph. Since a code with minimum distance $d$ corresponds to a $(d-1)$ -independent set in $\Gamma$ , these bounds provide upper limits on the code size $M$ .

Key Contributions

Spectral Characterization: The paper provides a general recursive expression for the eigenvalues of the multilinear forms graph for any order $m \ge 2$ . It proves that for $m \ge 3$ , the graph is not distance-regular, justifying the need for the eigenvalue method over Delsarte's scheme-based approach.
Explicit Spectrum for $2 \times 3 \times 3$ : The authors compute the complete spectrum (eigenvalues and multiplicities) of the multilinear forms graph for $2 \times 3 \times 3$ tensors over any finite field $\mathbb{F}_q$ . This is achieved by leveraging the classification of tensor orbits and subspace intersections.
Improved Bounds on Tensor Codes: Using the computed spectrum, the paper derives new upper bounds on the cardinality of tensor codes with minimum distances $d=3$ and $d=4$ for the $2 \times 3 \times 3$ case.
General Algorithmic Framework: The paper outlines a method to compute spectra for small parameters using enumeration of subspaces and provides a complementary repository with MAGMA and SageMath code to facilitate these computations.

Results

Spectral Properties: The spectrum of the graph is shown to depend on the intersection of subspaces with the Segre variety. For $2 \times 3 \times 3$ tensors, the spectrum consists of 12 distinct eigenvalues (for $q \ge 3$ ), with explicit formulas provided for their multiplicities.
Bounds for $d=3$ : For $2 \times 3 \times 3$ codes with minimum distance 3, the ratio-type bound yields $|C| < q^{12}(1 - 4q^{-1} + 12q^{-2})$ for $q \ge 3$ and $|C| < 2^{10.63}$ for $q=2$ . These results demonstrate that no such code can meet the Singleton-like bound ( $M \le q^{12}$ ).
Bounds for $d=4$ : For minimum distance 4, the paper establishes that for $q \in \{2, 3, 4\}$ , no code meets the Singleton-like bound ( $M \le q^9$ ). Specifically, for $q=2$ , $|C| \le 2^9 \frac{3780}{6426}$ .
Comparison with Existing Bounds: The derived ratio-type bounds are strictly sharper than the Singleton-like bound (Theorem 25) and its improved version (Theorem 26) for the specific parameters studied, particularly for small minimum distances. The paper notes that while the improved Singleton bound is better for large $d$ , the eigenvalue method provides superior bounds for small $d$ .
Empirical Observations: Numerical computations for various small parameters ( $q \in \{2, 3, 4, 5\}$ ) suggest that the ratio-type bound is a strict improvement over the Singleton bound for codes with minimum distances up to a certain threshold dependent on $q$ and the tensor dimensions.

Significance
The paper claims significance in extending the toolkit of algebraic coding theory to tensor codes, a domain where the "main coding theory problem" remains unsolved for higher orders. By demonstrating that the eigenvalue method can be successfully applied to non-distance-regular graphs generated by tensor rank metrics, the authors provide a viable alternative to Delsarte's framework. The explicit computation of the spectrum for $2 \times 3 \times 3$ tensors serves as a proof of concept, yielding tighter upper bounds on code sizes than previously known. The work highlights that the structure of tensor codes is deeply connected to the geometry of the Segre variety and the combinatorics of subspace intersections, offering a new perspective for analyzing tensor rank codes. The authors remain modest, noting that while their bounds improve upon existing ones for specific cases, the general problem of finding the maximum cardinality for arbitrary tensor codes remains open, and the computational complexity of determining the spectrum grows rapidly with parameters.

More like this