🔢 mathematics

Symmetric Tensor Decompositions over Finite Fields

This paper investigates the symmetric tensor rank of multiplication over finite field extensions by utilizing linearized polynomials and the Frobenius automorphism to reformulate the problem as explicit linear systems, thereby recovering known complexity values, providing new explicit decompositions, and establishing a connection to the symmetric tensor rank of Gabidulin codes.

Original authors: Giuseppe Cotardo, Ferdinando Zullo

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giuseppe Cotardo, Ferdinando Zullo

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 build a complex machine (a multiplication algorithm) using a limited set of basic Lego bricks. In the world of mathematics, specifically when working with "finite fields" (which are like tiny, self-contained universes of numbers), the goal is to multiply two numbers together using as few "bricks" as possible.

This paper is about finding the most efficient way to build this machine, but with a special rule: the machine must be perfectly symmetrical.

Here is a breakdown of what the authors did, using simple analogies:

1. The Big Problem: Building a Symmetrical Machine

Usually, when mathematicians try to multiply numbers in these tiny universes, they look for the shortest list of steps (called "tensor rank"). However, because multiplication is commutative (meaning $A \times B$ is the same as $B \times A$ ), the machine has a natural symmetry.

The authors ask: What is the absolute minimum number of steps needed if we force every single step to be perfectly symmetrical? This is called the symmetric tensor rank. It's like asking, "What is the shortest recipe for a cake if every ingredient must be added in a way that looks the same from the left and the right?"

2. The New Tool: "Linearized Polynomials" as Blueprints

To solve this, the authors didn't just look at the numbers directly. Instead, they used a special type of mathematical blueprint called linearized polynomials.

Think of these polynomials as a translator. They translate the messy problem of "multiplying numbers" into a cleaner problem of "drawing shapes."

The Translation: They showed that these polynomials are equivalent to symmetric matrices (grids of numbers that look the same if you fold them in half diagonally).
The Goal: They wanted to see if the "multiplication machine" could be built by stacking a few simple, single-layer shapes (called "rank-one" shapes) on top of each other.

3. The Method: Solving a Giant Puzzle

The authors turned the problem into a giant puzzle that can be solved with a calculator.

The Setup: They created a system of equations (a grid of numbers) based on the rules of the finite field.
The Trick: They used a mathematical tool called the Frobenius automorphism. Imagine this as a "magic mirror" that reflects the puzzle in a specific way. By looking at the puzzle and its reflection together, they could create a larger, more robust system of equations.
The Result: If this larger system has a solution, it means a symmetrical machine can be built with that specific number of steps. If it doesn't, that number of steps isn't enough.

4. What They Found (The Results)

The authors used this method to solve the puzzle for small universes (where the numbers are small, specifically for extension degrees 2, 3, and 4).

For Degree 2: They confirmed the machine needs 3 symmetrical steps. They even wrote down the exact "bricks" (the specific polynomials) needed to build it.
For Degree 3: They found that for small fields, the machine needs 6 steps. For larger fields, it can be done with 5. They provided the exact list of bricks for the 6-step version.
For Degree 4: They found that for fields of size 2, 3, 4, and 5, the machine needs between 8 and 9 steps. They provided the exact lists of bricks for these cases.

Essentially, they didn't just guess the numbers; they built the actual machines and showed you exactly how to assemble them.

5. The Coding Connection: A New Way to Look at Errors

The paper also connects this math to coding theory (the science of sending messages without errors).

They realized that the "multiplication machine" is actually a type of error-correcting code (specifically, a Gabidulin code).
They introduced a new way to measure these codes: Symmetric Tensor Rank.
The Insight: They showed that the difficulty of multiplying numbers is exactly the same as the difficulty of "covering" this specific code with simple, symmetrical shapes. It's like saying, "The complexity of the multiplication machine is the same as the complexity of the error-correcting code it lives inside."

Summary

In short, this paper is a construction manual.

It takes a hard problem (symmetrical multiplication) and translates it into a language of polynomials and grids.
It uses a mathematical mirror trick to turn the problem into a solvable equation.
It solves the equation for small cases, providing exact blueprints for how to build these symmetrical machines.
It reveals that these machines are secretly the same as certain error-correcting codes, giving mathematicians a new way to study both.

The authors didn't invent a new app or a medical device; they simply figured out the most efficient, symmetrical way to multiply numbers in tiny mathematical worlds and gave us the exact instructions to do it.

Technical Summary: Symmetric Tensor Decompositions over Finite Fields

Problem Statement
The paper addresses the problem of determining the symmetric tensor rank of the multiplication map $M_{q^m}: \mathbb{F}_{q^m} \times \mathbb{F}_{q^m} \to \mathbb{F}_{q^m}$ over finite field extensions. While the standard bilinear complexity $\mu_q(m)$ (the minimum number of non-scalar multiplications required) is a central topic in algebraic complexity theory, the symmetric tensor rank $\mu_q^{\text{sym}}(m)$ imposes an additional constraint: the two linear forms in each rank-one summand of the decomposition must coincide. Although $\mu_q^{\text{sym}}(m) \ge \mu_q(m) \ge 2m-1$ , determining exact values for $\mu_q^{\text{sym}}(m)$ remains difficult outside specific regimes (e.g., when $q \ge 2m-2$ ). Existing methods often rely on algebraic geometry or specific constructions, leaving a gap in constructive approaches for general parameters.

Methodology
The authors develop a constructive framework based on linearized polynomials (also known as $q$ -polynomials). The core methodology relies on establishing a rank-preserving correspondence between three mathematical objects:

Symmetric linearized polynomials in the algebra $L_{m,q}$ .
Symmetric bilinear forms on $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$ , defined via the field trace $\text{Tr}_{q^m/q}(xy)$ .
Symmetric matrices in $\mathbb{F}_q^{m \times m}$ .

The authors identify that a symmetric tensor decomposition of length $R$ corresponds to the existence of $R$ rank-one symmetric linearized polynomials that span the space of linearized polynomials representing the multiplication map. Specifically, they utilize the result that rank-one symmetric linearized polynomials take the form $\alpha \text{Tr}_{q^m/q}(\beta x)$ where $\alpha/\beta \in \mathbb{F}_q$ .

To transform this spanning condition into a computationally tractable problem, the authors:

Fix a generator $\xi$ of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$ .
Translate the spanning condition into a system of explicit linear equations over $\mathbb{F}_q$ .
Employ the Frobenius automorphism to enlarge these systems. By adjoining Frobenius conjugates of the equations, they derive a criterion where the existence of a solution in $\mathbb{F}_q^R$ guarantees a valid symmetric tensor decomposition. This enlargement ensures that solutions found are fixed by the Frobenius map, thus lying in the base field.

Key Contributions and Results

Constructive Criterion: The paper provides a necessary and sufficient condition for $\mu_q^{\text{sym}}(m) \le R$ in terms of the solvability of specific linear systems involving powers of elements in $\mathbb{F}_{q^m}$ and their Frobenius conjugates (Theorem 3.2).
Explicit Decompositions for Small $m$ : The authors apply their criterion to obtain explicit symmetric tensor decompositions for extension degrees $m \in \{2, 3, 4\}$ $m \in {2, 3, 4}$ :
- Case $m=2$ : They recover the known value $\mu_q^{\text{sym}}(2) = 3$ and provide an explicit decomposition involving three trace functions, valid for any $q$ .
- Case $m=3$ : They show that $\mu_q^{\text{sym}}(3) \le 6$ for all $q$ , with equality for $q \in \{2, 3\}$ . For $q \ge 4$ , the value is 5. They provide a method to find the required elements using the non-vanishing of a specific determinant polynomial.
- Case $m=4$ : Using computational verification (via MAGMA), they provide explicit decompositions for $q \in \{2, 3, 4, 5\}$ . They recover optimal values for $q=2$ ( $\mu=9$ ), $q=4$ ( $\mu=8$ ), and $q=5$ ( $\mu=8$ ), and provide a decomposition of length 9 for $q=3$ .
Coding-Theoretic Interpretation: The authors introduce the symmetric tensor rank of a symmetric rank-metric code, defined as the minimum number of rank-one symmetric matrices whose $\mathbb{F}_q$ -span contains the code. They demonstrate that the first-slice space of the multiplication tensor is equivalent to the one-dimensional Gabidulin code $G_1(m, q) = \langle x \rangle_{\mathbb{F}_{q^m}}$ . Consequently, $\mu_q^{\text{sym}}(m)$ is exactly the symmetric tensor rank of this specific Gabidulin code.

Significance
The paper claims significance in providing a constructive and algorithmic approach to symmetric tensor decompositions, moving beyond existence proofs or bounds derived from algebraic geometry. By reformulating the problem as a linear algebraic problem over finite fields involving Frobenius-stable systems, the authors offer a practical method for:

Verifying candidate decompositions.
Producing explicit examples for parameters where exact values were previously unknown or only bounded.
Bridging the gap between tensor rank theory and rank-metric coding theory, specifically by interpreting the symmetric tensor rank of multiplication as an invariant of symmetric rank-metric codes.

The authors note that while their method successfully handles small extension degrees, determining exact values for larger $m$ and finding uniform families of elements satisfying the linear conditions remain open challenges. The framework is presented as a tool for further investigation into the symmetric bilinear complexity of finite field multiplication.