Quasi-twisted codes and their connection with additive constacyclic codes over finite fields

This paper establishes a polynomial-based framework linking quasi-twisted codes over finite fields to additive constacyclic codes, providing a one-to-one correspondence that enables the characterization of their respective duals and self-orthogonality conditions through trace and standard inner products.

The Gist

Imagine you are a master architect designing a fortress to protect valuable information. In the world of coding theory, this "fortress" is a code—a set of rules that turns your data into a sequence of numbers (like a secret language) so that if some numbers get lost or corrupted during transmission, the message can still be recovered.

This paper is about two specific types of architectural blueprints for these fortresses: Quasi-Twisted Codes and Additive Constacyclic Codes. The authors, Kanat Abdukhalikov and Gyanendra Verma, have discovered a secret tunnel connecting these two seemingly different designs, allowing them to solve complex problems in one world by looking at the other.

Here is a simple breakdown of their discoveries:

1. The Two Types of Fortresses

The "Twisted" Fortress (Quasi-Twisted Codes)
Imagine a long line of soldiers standing in a circle.

• In a standard Cyclic Code, if you tell everyone to take one step to the right, the person at the very end wraps around to the front. The formation stays perfect.
• In a Quasi-Twisted Code, the soldiers are arranged in groups (like squads). When you shift them, the whole squad moves, but the last squad doesn't just wrap around; it gets a little "twist" or "flip" (like a soldier turning around or changing their uniform color) before rejoining the front.
• Why it's cool: These codes are incredibly flexible and can be built to be very strong (good at catching errors) and very efficient.

The "Additive" Fortress (Additive Constacyclic Codes)
Now, imagine a different kind of fortress built on a larger, more complex grid (like a 2D chessboard instead of a 1D line).

• These codes are "Additive," meaning they follow the rules of addition but not necessarily the strict rules of multiplication (scaling).
• They are often built over "extension fields," which is like speaking a language that has more letters than the standard alphabet.
• Why it's cool: Sometimes, these additive fortresses are stronger than the standard linear ones. They can protect data better, even when no standard linear code exists for that specific job.

2. The Big Discovery: The Secret Tunnel

The main point of this paper is that these two fortresses are actually the same building, just viewed from different angles.

The authors found a one-to-one correspondence. Think of it like this:

• If you have a "Twisted" fortress with 2 squads (index 2) built on a simple alphabet, you can translate it perfectly into an "Additive" fortress built on a double-sized alphabet.
• The "index" (how many squads you have) tells you exactly how much bigger the alphabet needs to be for the Additive version.

The Magic Translation:
The authors created a mathematical "dictionary" (using polynomials) to translate between these two worlds.

• Euclidean vs. Symplectic: In the Twisted world, they measure "distance" or "orthogonality" (how different two codes are) using a standard ruler (Euclidean) or a special cross-check (Symplectic).
• Trace vs. Hermitian: In the Additive world, they use a different kind of ruler called a "Trace" ruler.
• The Breakthrough: They proved that checking if two Additive codes are "orthogonal" (safe from each other) using the Trace ruler is exactly the same as checking if their corresponding Twisted codes are orthogonal using the Euclidean or Symplectic rulers.

3. Why Does This Matter? (The "So What?")

This connection is a superpower for engineers and mathematicians for three main reasons:

A. Building Better Quantum Computers
Quantum computers are very fragile; they need special "Quantum Codes" to survive errors. A popular way to build these is by taking two classical codes that fit together perfectly (like a lock and key).

• The authors showed that if you can find a "Twisted" code that fits with its own dual (a self-orthogonal code), you can instantly translate that into a powerful Additive code for quantum computing.
• They even gave a recipe (a list of polynomial rules) to build these codes so they are guaranteed to work.

B. Finding the "Best" Codes
Sometimes, the best possible code for a job doesn't exist in the "Linear" world. But it might exist in the "Additive" world.

• By using their translation tool, the authors found several new codes that are better than any previously known linear codes.
• Analogy: It's like realizing that to build the strongest bridge, you don't need to use steel beams (Linear); you can use a specific type of woven rope (Additive) that is stronger, and they showed you exactly how to weave it.

C. Simplifying the Math
Before this paper, studying these Additive codes was like trying to solve a puzzle in the dark. You had to use complex "Trace" formulas that were hard to visualize.

• Now, researchers can take the Additive problem, translate it into the Twisted world (where the math is more familiar and easier to handle), solve it there, and translate the answer back. It's like using a map you already know to navigate a new city.

Summary Analogy

Imagine you are a chef trying to bake the perfect cake.

• Quasi-Twisted Codes are like baking in a standard oven using standard flour.
• Additive Codes are like baking in a high-tech sous-vide machine using a special exotic flour.
• The Paper says: "Hey, the special exotic flour cake is actually just the standard cake with a different recipe! If you know how to bake the standard cake perfectly, you can instantly know how to bake the exotic one."

They provided the recipe book (the polynomial formulas) that tells you exactly how to mix the ingredients (the polynomials) to get a cake that is:

1. Self-protecting (Self-orthogonal).
2. Perfect for Quantum Computers.
3. Better than anything we had before.

In short, this paper bridges two worlds of mathematics, making it much easier to build the next generation of error-correcting codes that will keep our data safe in the future.

Technical Summary

Here is a detailed technical summary of the paper "Quasi-twisted codes and their connection with additive constacyclic codes over finite fields" by Kanat Abdukhalikov and Gyanendra K. Verma.

1. Problem Statement

The paper addresses two primary challenges in coding theory:

1. Structural Characterization: While quasi-cyclic codes are well-understood, quasi-twisted (QT) codes (a generalization including cyclic, constacyclic, and quasi-cyclic codes) have not been thoroughly explored using a polynomial-based approach without decomposing them into constituent codes via the Chinese Remainder Theorem (CRT). Existing literature often relies on CRT decomposition or is limited to single-generator QT codes.
2. Duality and Correspondence: There is a need to establish a rigorous connection between quasi-twisted codes over a finite field $\mathbb{F}_q$ and additive constacyclic codes over an extension field $\mathbb{F}_{q^l}$. Specifically, the authors aim to determine the duals of additive constacyclic codes (under trace inner products) by leveraging the known duals of their corresponding quasi-twisted codes.

2. Methodology

The authors employ a polynomial-based algebraic approach to analyze the structure of codes. Key methodological steps include:

• Polynomial Representation: Instead of decomposing codes into constituent codes, the authors represent QT codes of length $lm$ and index $l$ as submodules of $(\mathbb{F}_q[x]/\langle x^m - \lambda \rangle)^l$. They focus specifically on the case where the index $l=2$.
• Generator Matrices: They characterize QT codes of index 2 using a specific set of polynomial generators (a "Hermite Normal Form" style basis) consisting of two elements: $g_1 = (g_{11}(x), g_{12}(x))$ and $g_2 = (0, g_{22}(x))$.
• Inner Product Definitions: The paper defines and analyzes three types of inner products:
  • Euclidean: Standard dot product.
  • Symplectic: Defined as $\langle (a,b), (a',b') \rangle_s = \langle a, b' \rangle_e - \langle b, a' \rangle_e$.
  • Hermitian: Defined over $\mathbb{F}_{q^2}$ using conjugation.
  • Trace Inner Products: Defined for additive codes over extension fields (Trace Euclidean and Trace Hermitian).
• Correspondence Mapping: A bijection $\phi$ is constructed between a QT code $C$ of length $2m$over$\mathbb{F}q$and an additive constacyclic code$C_A$of length$m$over$\mathbb{F}{q^2}$. This mapping relies on a basis${w_1, w_2}$of$\mathbb{F}_{q^2}$over$\mathbb{F}_q$.
• Basis Selection: The authors utilize almost self-dual and self-dual bases to simplify the relationship between the trace inner products in the additive setting and the standard inner products in the QT setting.

3. Key Contributions

A. Polynomial Characterization of Index-2 QT Codes

• Theorem 3.1: The authors provide a necessary and sufficient condition for a set of polynomials to generate a QT code of index 2. They prove that any such code is generated by two specific polynomials satisfying degree constraints and divisibility conditions (e.g., $g_{11}g_{22} \mid (x^m-\lambda)g_{12}$).
• Single-Generator Condition: They establish that a QT code of index 2 is generated by a single element if and only if $g_{11}(x)g_{22}(x) \equiv 0 \pmod{x^m - \lambda}$ (under the condition $\gcd(m,q)=1$).

B. Determination of Dual Codes

The paper explicitly constructs the generators for the duals of index-2 QT codes:

• Euclidean Dual ($C^{\perp_e}$): Derived in Theorem 4.4, providing explicit polynomial generators for the dual code based on the reciprocal polynomials of the original generators.
• Symplectic Dual ($C^{\perp_s}$): Derived in Theorem 5.1, showing how the symplectic dual is generated by a specific permutation and transformation of the original generators.
• Hermitian Dual ($C^{\perp_h}$): Derived in Theorem 6.4 for codes over $\mathbb{F}_{q^2}$, utilizing conjugate reciprocal polynomials.

C. Self-Orthogonality Conditions

The authors derive necessary and sufficient conditions for a QT code to be self-orthogonal (contained in its dual) under Euclidean, Symplectic, and Hermitian inner products (Theorems 7.1, 7.2, 7.3). These conditions are expressed as polynomial congruences involving the generators and their reciprocals/conjugates.

D. Correspondence with Additive Constacyclic Codes

• One-to-One Mapping: The paper proves that QT codes of length $lm$ and index $l$ over $\mathbb{F}_q$ are isomorphic to additive constacyclic codes of length $m$ over $\mathbb{F}_{q^l}$.
• Dual Equivalence: This is the paper's most significant theoretical contribution. The authors demonstrate that:
  • The Trace Euclidean dual of an additive constacyclic code corresponds to the Euclidean dual of the corresponding QT code (under specific basis conditions).
  • The Trace Hermitian dual of an additive constacyclic code corresponds to the Symplectic dual of the corresponding QT code (when $q$ is even) or a scaled Euclidean dual (when $q$ is odd).
• Generalization: These results generalize previous findings on additive cyclic codes (where index $l=1$) to arbitrary indices and constacyclic settings.

4. Key Results and Examples

• Explicit Generators: The paper provides explicit formulas for the generators of dual codes, moving beyond implicit existence proofs found in earlier literature.
• Quantum Code Construction: Using the derived self-orthogonality conditions and the CSS construction method, the authors construct quantum error-correcting codes. Example 7.4 demonstrates a $[[10, 2, 4]]_4$ quantum code derived from QT codes, matching the best-known parameters.
• Optimal Classical Codes: Tables 1 and 2 list several QT codes over ternary and quaternary fields that achieve parameters matching the Best Known Linear Codes (BKLC).
• Additive vs. Linear Superiority: Example 9.1 and Table 3 illustrate that additive constacyclic codes can achieve parameters (length, size, minimum distance) that no linear cyclic codes can match. For instance, an additive code with parameters $(71, 2^{106}, 8)_4$ exists, whereas no linear cyclic code with parameters $[71, 53]_4$ exists.

5. Significance

• Unified Framework: The paper unifies the study of quasi-twisted codes and additive constacyclic codes, showing that the complex problem of finding duals for additive codes over extension fields can be reduced to the more tractable problem of finding duals for linear codes over the base field.
• Algorithmic Utility: By providing explicit polynomial generators for duals, the results facilitate efficient encoding and decoding algorithms for these code families.
• Quantum Coding: The findings provide a robust theoretical foundation for constructing new quantum stabilizer codes, which rely heavily on self-orthogonal classical codes.
• Code Construction: The identification of QT codes with optimal parameters and the demonstration of additive codes outperforming linear codes highlight the practical value of these generalized code classes in modern communication and storage systems.

In conclusion, Abdukhalikov and Verma successfully bridge the gap between the algebraic structure of quasi-twisted codes and additive constacyclic codes, providing a powerful toolkit for constructing and analyzing high-performance error-correcting codes for both classical and quantum applications.