💻 computer science

On Binary Codes That Are Maximal Totally Isotropic Subspaces with Respect to an Alternating Form

This paper introduces an alternating form on binary vector spaces to study and classify maximal totally isotropic codes for lengths up to 24, while establishing a MacWilliams-type identity and deriving constraints on their weight enumerators.

Original authors: Patrick King, Mikhail Kotchetov

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Patrick King, Mikhail Kotchetov

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 organizing a massive party where every guest is represented by a string of light switches (on or off). In the world of computer science, these strings are called binary codes. Usually, when we want to check if two guests "get along" (mathematically, if they are orthogonal), we use a standard rule: we multiply their switches together and add them up. If the total is zero, they are considered a perfect pair.

For decades, mathematicians have been obsessed with finding groups of guests who are all perfect pairs with each other. These special groups are called self-dual codes. They are like a club where everyone fits perfectly with everyone else, and the club is so balanced that it equals its own "shadow" (its mathematical dual).

The New Twist: A Different Kind of "Getting Along"

In this paper, authors Patrick King and Mikhail Kochetov ask a simple question: What if we change the rules of how guests get along?

Instead of the standard rule, they introduce a new, slightly quirky rule called an alternating form. Under this new rule, a guest is always considered "compatible" with themselves (mathematically, the value is always zero). This creates a different kind of mathematical landscape.

The authors are looking for the largest possible groups of guests who are all compatible with each other under this new rule. They call these groups maximal totally isotropic subspaces. Think of it as finding the biggest possible dance floor where everyone can dance with everyone else without stepping on toes, but using a new, weird dance step.

The Big Discovery: Odd vs. Even Lengths

The paper splits the problem into two scenarios based on the number of guests (the length of the code):

Odd Number of Guests: When the party has an odd number of people, the new rule has a "glitch" (mathematically, it's degenerate). The authors found that these groups are essentially just the old, standard "perfect pair" groups with one extra person added to the mix. They classified all these groups for parties up to 24 people.
Even Number of Guests: When the party has an even number of people, things get interesting.
- Some groups are just the old "self-dual" clubs we already knew about.
- The Surprise: There are new groups (called "odd Lagrangians") that contain people with an odd number of "on" switches. The authors were shocked to find that some of these new groups are actually better at correcting errors than the best-known old groups. In some cases, these new groups can detect and fix more mistakes than the famous "Hamming codes" we've used for years.

The "Magic Formula" (MacWilliams Identity)

In the world of coding, there is a famous magic formula (the MacWilliams identity) that lets you predict the properties of a group's "shadow" just by looking at the group itself.

The authors discovered that the old magic formula doesn't work for their new rule. However, they didn't give up. They invented a new magic formula specifically for their alternating rule. This new formula allows them to calculate the properties of the "shadow" group, even though the rules have changed.

Why This Matters (According to the Paper)

The authors didn't just find these groups; they classified them. They made a complete list of every unique type of these groups for parties up to 24 people.

They created a "menu" (Table 1 in the paper) showing how many different types of these groups exist for each party size.
They proved that for certain party sizes, these new groups can have a higher "minimum distance" (a measure of how robust the code is) than the best self-dual codes we already knew.
They used their new magic formula to set strict rules on what these groups can look like, essentially narrowing down the infinite possibilities to a manageable set of shapes.

In a Nutshell

Think of this paper as a guidebook for a new type of dance floor. The authors:

Changed the dance steps (the inner product).
Found the biggest possible dance circles (maximal isotropic subspaces) that work with these new steps.
Discovered that some of these new circles are surprisingly better dancers (better error correction) than the old champions.
Wrote a new rulebook (the new MacWilliams identity) to help predict how these new dance circles behave.

They have mapped out the entire landscape for small groups (up to 24 people), showing us that there are many more ways to build these perfect mathematical structures than we previously thought.

Technical Summary: On Binary Codes That Are Maximal Totally Isotropic Subspaces with Respect to an Alternating Form

Problem Statement
While self-dual binary linear codes (where a code $K$ equals its orthogonal complement $K^\perp$ under the standard dot product) have been extensively studied and classified for lengths $n \le 40$ , there is a lack of research regarding linear codes that coincide with their orthogonal complement when the underlying inner product is not the standard dot product. This paper addresses the classification and structural properties of binary linear codes that are maximal totally isotropic subspaces with respect to a specific alternating bilinear form defined on $\mathbb{F}_2^n$ .

Methodology
The authors define a new inner product on the vector space $V = \mathbb{F}_2^n$ :
$\langle v, w \rangle := \sum_{i \neq j} v_i w_i = v \cdot w + p(v)p(w)$
where $v \cdot w$ is the standard dot product and $p(v) = \sum v_i$ is the parity of the vector. Unlike the dot product, this form is alternating ( $\langle v, v \rangle = 0$ for all $v$ ).

The study proceeds through the following methodological steps:

Classification via Symplectic Geometry: The authors analyze the structure of maximal totally isotropic subspaces (Lagrangians) under this form.
- For odd $n$ , the form is degenerate with a radical spanned by the all-ones vector $\mathbf{1}$ . The authors establish a bijection between maximal totally isotropic subspaces of $\mathbb{F}_2^n$ and maximally self-orthogonal codes of length $n$ .
- For even $n$ , the form is non-degenerate, making $\mathbb{F}_2^n$ a symplectic space. The authors distinguish between "even" Lagrangians (subspaces contained in the even-weight subspace $V^+$ , which correspond to standard self-dual codes) and "odd" Lagrangians (those containing vectors of odd weight). They utilize a two-to-one correspondence between odd Lagrangians and complements of $\langle \mathbf{1} \rangle$ within even Lagrangians to facilitate classification.
Computational Classification: Using SageMath, the authors implement an algorithm to classify these subspaces up to the action of the symmetric group $S_n$ (permuting coordinates) for $n \le 24$ . This involves generating representatives of self-dual codes, finding their complements, and constructing the corresponding odd Lagrangians. A mass formula is used to verify the completeness of the enumeration.
Weight Enumerator Analysis: The authors derive a MacWilliams-type identity specific to this alternating inner product. They analyze the weight enumerators of these codes by studying the action of specific matrix groups (isomorphic to the dihedral group $D_8$ and a larger group of order 192) on the space of polynomials. This allows them to determine the algebraic structure of the weight enumerators for both general and Type II (weights divisible by 4) cases.

Key Contributions and Results

Classification: The paper provides a complete classification of maximal totally isotropic subspaces for $n \le 24$ $n \leq 24$ . The results are presented in Table 1, enumerating the number of inequivalent Type I and Type II Lagrangians for both odd and even lengths.
- Notably, for certain values of $n$ , the minimum distance of specific odd Lagrangians exceeds the highest minimum distance achievable by standard self-dual codes of the same length.
MacWilliams-Type Identity: The authors prove that the standard MacWilliams identity does not hold for this alternating form. Instead, they derive a modified identity (Proposition 4.2) relating the weight enumerator of a code $K$ to that of its orthogonal complement $K^\perp$ . This identity separates the even and odd parts of the weight enumerator, showing that the odd part undergoes a variable swap ( $x \leftrightarrow y$ ) in the transformation.
Structural Constraints on Weight Enumerators:
- Odd Length: The authors prove that the weight enumerator of a maximal totally isotropic code of odd length is determined by the weight enumerator of its even part. They provide explicit module structures for these enumerators over the ring of invariants, distinguishing between general cases and Type II cases (where weights are divisible by 4).
- Even Length: For even $n$ , the paper establishes constraints on the weight enumerators of odd Lagrangians. It demonstrates that for Type II odd Lagrangians, the length $n$ must satisfy specific congruences modulo 8 ( $n \equiv 0, 2, \text{ or } -2 \pmod 8$ ).
- The paper provides detailed theorems (4.7, 4.9, 4.13, 4.19, 4.21, 4.23) describing the weight enumerators as elements of free modules generated by specific polynomials over the ring of invariants.
Decomposition Properties: The paper characterizes decomposable maximal totally isotropic subspaces. It shows that a code with minimum distance 1 or 2 decomposes into a direct product involving smaller codes (e.g., $i_1 \times M$ or $i_2^k \times M$ ), allowing for recursive analysis.

Significance
The paper claims significance in filling a gap in the literature regarding linear codes that are self-orthogonal under non-standard inner products. By introducing the alternating form $\langle v, w \rangle = v \cdot w + p(v)p(w)$ , the authors open a new avenue for studying "Lagrangian" subspaces in binary vector spaces.

The work is significant because:

It extends the theory of self-dual codes to a broader context of alternating forms, revealing new classes of codes (odd Lagrangians) with potentially superior minimum distances compared to traditional self-dual codes.
It provides the first complete classification of these structures for small lengths ( $n \le 24$ ).
It establishes a theoretical framework (via the new MacWilliams-type identity) for analyzing the weight distributions of these codes, proving that their enumerators are constrained by specific algebraic invariants similar to, but distinct from, those of standard self-dual codes.

The authors note that the classification of odd Lagrangians is equivalent to classifying maximally self-orthogonal codes of odd length, thereby linking this study to existing problems in coding theory while offering new structural insights through the symplectic geometry perspective.

More like this