🔢 mathematics

Double Toeplitz codes and their average weight enumerators

This paper investigates the average weight enumerators of double Toeplitz codes, applying these results to establish the existence of such codes with specified minimum weights over $\mathbb{F}_q$ for $q \in \{2,3,4\}$ and providing a classification of those with the largest minimum weights for modest lengths.

Original authors: Masaaki Harada, Keito Yamaguchi

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Masaaki Harada, Keito Yamaguchi

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 master architect trying to build the most secure, efficient, and compact storage facility possible. In the world of mathematics and computer science, these "storage facilities" are called codes. They are used to send messages (like photos, videos, or text) across the internet or space without them getting corrupted by noise or interference.

The goal is to pack as much information as possible into a small space while ensuring that if a few bits of data get scrambled, the original message can still be perfectly recovered. The "strength" of this protection is measured by something called the minimum weight. Think of this as the "distance" between two valid messages. The further apart they are, the harder it is for noise to turn one valid message into another by accident.

The Problem: Finding the Best Blueprint

For decades, mathematicians have been looking for the best possible blueprints (codes). Two famous types of blueprints are:

Double Circulant Codes: These are like patterns that repeat in a perfect circle. If you shift the pattern, it looks the same. They are very structured and easy to build.
Double Negacirculant Codes: Similar to the above, but with a slight twist (like a mirror reflection) in the pattern.

Recently, mathematicians discovered a more flexible type of blueprint called Double Toeplitz Codes.

The Analogy: Imagine a Toeplitz matrix as a wall made of bricks where every diagonal line of bricks is identical. It's less rigid than a perfect circle (circulant) but still has a very strong, predictable structure.
The Promise: Because they are less rigid, they might allow us to build stronger walls (codes with higher minimum weights) than the old circular designs.

The Challenge: Too Many Possibilities

The problem with these new Toeplitz codes is that there are billions of possible variations. Trying to check every single one by hand (or even by computer) to see which one is the strongest is like trying to find the perfect needle in a haystack the size of a city.

The Solution: The "Average" Approach

Instead of checking every single code one by one, the authors of this paper (Masaaki Harada and Keito Yamaguchi) used a clever statistical trick.

The Metaphor: The Weather Forecast
Imagine you want to know if it will rain tomorrow in a specific city. You could try to predict the weather for every single street corner, which is impossible. Instead, you look at the average weather patterns for the whole city. If the average forecast says "high chance of rain," you know it's likely to rain somewhere.

The authors did something similar:

They calculated the Average Weight Enumerator. This is a mathematical formula that tells them, "On average, how strong are these codes?"
They didn't need to list every single code to do this. They used a formula to predict the "average strength" of the entire family of Toeplitz codes.
The Logic: If the average strength of the codes is high enough, it proves that at least one code in that group must be very strong. It's like saying, "If the average height of people in a room is 6 feet, there must be someone in there who is at least 6 feet tall."

What They Found

Using this "average" method and powerful computers, they explored codes over three different types of number systems (Binary, Ternary, and Quaternary—think of them as languages with 2, 3, or 4 letters).

Here are their key discoveries:

Proving Existence: They proved that for many different lengths of messages, there definitely exist Double Toeplitz codes that are stronger than previously thought. They gave specific "lengths" (sizes of the storage facility) where these strong codes exist.
The "New" Champions: They found many specific codes that are the strongest possible for their size (called DT-optimal).
Breaking the Mold: The most exciting part? Many of these new "champion" codes cannot be built using the old circular (circulant) or twisted (negacirculant) methods. They are genuinely new structures.
- Analogy: It's like discovering a new type of bridge design that is stronger than any suspension or arch bridge we've ever built before.

Why Does This Matter?

In the real world, better codes mean:

Faster Internet: Sending more data with less error correction overhead.
Deeper Space Exploration: Sending clearer pictures from Mars or Jupiter with less power.
Secure Storage: Hard drives that are less likely to lose data due to corruption.

Summary

Think of this paper as a map. The authors didn't just walk every path in a forest; they used a satellite view (the average weight enumerator) to prove that a treasure (a super-strong code) exists in a specific area. Then, they went in and dug up the treasure, showing us that these new "Toeplitz" structures are not just theoretical ideas—they are real, powerful tools that outperform the old standards.

They have essentially handed engineers a new set of blueprints that are stronger, more efficient, and previously unknown.

1. Problem Statement

The paper addresses the construction and classification of double Toeplitz codes, a generalization of double circulant and double negacirculant codes. These codes are significant because they are isodual (equivalent to their duals) and often possess large minimum weights, making them candidates for optimal error-correcting codes.

The core problems tackled in this research are:

Theoretical Analysis: Deriving an explicit formula for the average weight enumerator of the set of all distinct double Toeplitz codes over a finite field $\mathbb{F}_q$ without needing to enumerate the entire set.
Existence: Determining the existence of double Toeplitz codes with specific minimum weights ( $d$ ) for lengths $n$ and fields $q \in \{2, 3, 4\}$ .
Classification: Classifying DT-optimal codes (those achieving the largest possible minimum weight $d_{q,DT}(n)$ ) for modest lengths and identifying which of these are inequivalent to existing double circulant or double negacirculant codes.

2. Methodology

Theoretical Framework

Definitions: A double Toeplitz code $DT(t, a, b)$ is defined by a generator matrix $(I_{n/2} \mid T(t, a, b))$ , where $T$ is a Toeplitz matrix determined by a scalar $t$ and two vectors $a$ and $b$ .
Average Weight Enumerator: The authors define $\Psi_{q,n}(y)$ as the sum of weight enumerators of all distinct double Toeplitz codes in the set $\Omega_{q,n}$ .
Combinatorial Counting (Lemma 3.2 & Theorem 3.3):
- Instead of listing all codes, the authors count how many codes contain a specific vector $(u, v)$ .
- They utilize the parity-check matrix condition $A^T u^T = v^T$ (where $A$ is the Toeplitz part) to determine the number of solutions for the parameters $(t, a, b)$ .
- They derive an explicit closed-form expression for $\Psi_{q,n}(y)$ based on the weight of vectors $u$ and $v$ . This formula allows the calculation of the average number of codewords of a specific weight across the entire family of codes.

Existence Proofs

Proposition 3.4: Using the derived average weight enumerator, the authors apply a probabilistic method. If the sum of the coefficients of the average weight enumerator for weights less than $d$ is strictly less than the total number of codes multiplied by $(q-1)$ , then there must exist at least one double Toeplitz code with minimum weight at least $d$ .

Computational Classification

Exhaustive Search: For specific lengths and fields, the authors performed exhaustive computer searches using Magma.
Equivalence Reduction: To manage the computational complexity, they employed reduction lemmas (Lemma 5.1, 5.2, 5.3) to normalize the parameters $(t, a, b)$ $(t, a, b)$ :
- Scaling by non-zero field elements.
- Swapping vectors $a$ and $b$ (due to isoduality).
- Ordering vectors to avoid checking equivalent permutations.
Comparison: The classified codes were compared against known double circulant and double negacirculant codes to identify new, inequivalent structures.

3. Key Contributions

Explicit Average Weight Enumerator Formula: The paper provides the first theoretical expression for the average weight enumerator of double Toeplitz codes (Theorem 3.3). This formula depends only on $n$ , $q$ , and combinatorial terms, bypassing the need to generate the set of codes.
Existence Bounds: The authors established precise lower bounds on the length $n$ required to guarantee the existence of double Toeplitz codes with minimum weights $d$ for $d \le 10$ over $\mathbb{F}_2, \mathbb{F}_3,$ and $\mathbb{F}_4$ .
Correction of Previous Data: The authors identified and corrected an error in a previous study ([20]) regarding the maximum minimum weight of ternary double Toeplitz codes of length 28, proving $d_{3,DT}(28) = 9$ (previously reported as 8, but the paper clarifies the existence of a weight 9 code and the non-existence of weight 10).
Discovery of New Optimal Codes: The classification reveals a vast number of DT-optimal codes that are inequivalent to double circulant or double negacirculant codes. This expands the known library of optimal isodual codes.

4. Key Results

Existence of Codes with Specified Minimum Weights

The paper determines the minimum length $n_q(d)$ required for a double Toeplitz code over $\mathbb{F}_q$ to have minimum weight at least $d$ :

Binary ( $q=2$ ): Codes with $d \ge 5$ exist for $n \ge 16$ ; $d \ge 8$ for $n=24$ and $n \ge 28$ .
Ternary ( $q=3$ ): Codes with $d \ge 5$ exist for $n \ge 10$ ; $d \ge 9$ for $n=24$ and $n \ge 28$ .
Quaternary ( $q=4$ ): Codes with $d \ge 5$ exist for $n \ge 10$ ; $d \ge 10$ for $n \ge 28$ .
Note: For many specific small lengths, the authors explicitly verified non-existence (e.g., no binary code with $d=5$ for $n \le 14$ ).

Classification of DT-Optimal Codes

The authors classified the number of inequivalent DT-optimal codes for various lengths:

Binary: For lengths up to 40. For example, at $n=38$ , there are 118,328 inequivalent DT-optimal codes that are not double circulant, compared to 415 double circulant ones.
Ternary: For lengths up to 26. At $n=18$ , there are 156,189 inequivalent DT-optimal codes not equivalent to double circulant or negacirculant codes.
Quaternary: For lengths up to 20 (excluding 16 due to computational limits). At $n=14$ , there are 360 such codes.

Specific Optimal Values

$d_{3,DT}(28)$ : Corrected to 9.
$d_{4,DT}(n)$ for $n \in \{16, 18, 20, 22, 24\}$ : Determined to be 6, 7, 8, 8, 9 respectively.

5. Significance

Expansion of Code Families: The study demonstrates that double Toeplitz codes are a rich source of new isodual codes. The sheer number of inequivalent codes found (often orders of magnitude larger than double circulant codes) suggests that restricting research to circulant structures misses a vast space of optimal codes.
Methodological Advancement: The derivation of the average weight enumerator without explicit enumeration provides a powerful tool for future coding theory research. It allows researchers to predict the existence of optimal codes in large families where exhaustive search is computationally infeasible.
Practical Implications: By identifying specific parameters $(t, a, b)$ for optimal codes, the paper provides concrete constructions for potential use in communication systems requiring high error correction capabilities with specific structural properties (isoduality).
Open Questions: The paper raises the question of whether $d_{q,DT}(n)$ can strictly exceed $d_{q,DC}(n)$ (the best double circulant weight) for $q \in \{2, 4\}$ , suggesting that double Toeplitz codes may offer superior performance in certain regimes.

In summary, this paper bridges theoretical combinatorics and computational coding theory to significantly advance the understanding of double Toeplitz codes, providing both a general existence theorem and a detailed catalog of optimal codes for small to moderate lengths.