🔢 mathematics

Perfect $2$-codes over arbitrary alphabets

This paper confirms the conjecture that no perfect 2-codes exist over non-prime-power alphabets for specific cases, including when the alphabet size is of the form $q=2^\alpha p^\beta$ with $\alpha \leq 20$ or sufficiently large.

Original authors: Michael A. Bennett

Published 2026-07-31

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael A. Bennett

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 sending a secret message across a noisy, chaotic galaxy. Every time you transmit a letter, a mischievous space goblin might swap it for a different one, or drop it entirely. To survive this chaos, you don't just send the message once; you send it with extra "spare parts" built right into the code. This is the world of error-correcting codes, the invisible shield that keeps your text messages, space probes, and streaming videos from turning into gibberish.

In this universe, a "perfect code" is the holy grail. It's like a packing puzzle where you have a giant box (all possible messages) and you try to fit in as many "safe zones" (your actual messages) as possible. Each safe zone has a radius of protection around it. If a message gets hit by a goblin and changes slightly, it still lands inside one of these safe zones, and the receiver knows exactly which original message it was. A code is "perfect" if these safe zones fit together like a jigsaw puzzle with absolutely no gaps and no overlaps. If the puzzle has gaps, you might lose a message; if it overlaps, you might get confused about which message was sent.

For decades, mathematicians have been trying to solve the ultimate version of this puzzle: finding perfect codes that can fix two errors at once (a "perfect 2-code") using an alphabet of any size. While they found the perfect solutions for fixing three or more errors, and for fixing one error, the case for fixing exactly two errors with a "weird" alphabet size (one that isn't a simple power of a prime number, like 10 or 15) has remained a stubborn, unsolved mystery. It's the difference between knowing how to pack a suitcase perfectly with 2, 4, or 8 items, but having no idea if it's possible to do it perfectly with 6 or 10 items.

This paper, written by Michael Bennett, dives deep into that specific mystery. The author sets out to prove that for a very large and specific family of "weird" alphabet sizes, perfect 2-codes simply do not exist. The paper doesn't just guess; it uses a heavy artillery of advanced mathematics—specifically tools that measure how close numbers can get to each other without actually touching—to show that if such a code did exist, it would have to be so incredibly massive and strange that it would break the laws of arithmetic.

The main finding is a powerful "no-go" zone. Bennett proves that if you try to build a perfect 2-code using an alphabet size made of a power of 2 multiplied by a power of a single prime number (like $2^\alpha \times p^\beta$ ), you are out of luck. Specifically, he shows that for these codes to even be theoretically possible, the prime number involved would have to be larger than $10^{10}$ (ten billion), and the power of 2 would have to be larger than 20. Furthermore, if such a code existed, the prime number would have to leave a remainder of 3 when divided by 8.

The paper goes even further. It rules out the existence of these perfect codes for any alphabet size where the largest prime factor is 13 or smaller. In fact, the author confirms a long-standing conjecture that no perfect 2-codes exist for many specific numbers, including cases where the alphabet size is $2^\alpha \times p^\beta$ with small values of $\alpha$ (up to 20). The author doesn't just say "it's unlikely"; he uses rigorous mathematical proofs to demonstrate that the conditions required for such a code to exist lead to mathematical contradictions. While the paper doesn't rule out every single possible alphabet size in the universe, it effectively closes the door on the most common and interesting "weird" sizes, leaving only a tiny, highly constrained sliver of possibility that would require numbers so large they are practically unimaginable.

The Story of the Impossible Puzzle

To understand what Michael Bennett did, let's look at the puzzle he was trying to solve. Imagine you have a giant grid of all possible words you can make with a certain alphabet. You want to place "beacons" (your code words) on this grid. Around each beacon, you draw a circle that covers all words that are "close enough" (within a distance of 2 errors). For a code to be perfect, these circles must cover the entire grid without overlapping.

Mathematicians have known for a long time that if your alphabet size is a "prime power" (like 2, 3, 4, 8, 9, 16), there are only a few special cases where this works perfectly. But what if your alphabet size is something like 10, 12, or 20? These are "composite" numbers that aren't prime powers. For fixing one error, we know some solutions exist. For fixing three or more errors, we know none exist. But for fixing two errors? That was the open question.

Bennett's paper focuses on a specific type of composite number: those that look like $2^\alpha \times p^\beta$ . Think of this as an alphabet size made by multiplying a bunch of 2s by a bunch of copies of a single prime number $p$ (like 5, 7, 11, etc.). The question was: Can you build a perfect 2-code for these sizes?

The Mathematical Detective Work

Bennett didn't just try to build the codes and fail; he proved they couldn't exist by looking at the "roots" of a special polynomial equation. Think of this equation as a map that tells you where the beacons must be if a perfect code exists. If a perfect code exists, this map must have two specific integer points (roots) that are very close to each other.

The author's breakthrough was realizing that these two points, let's call them $r_1$ and $r_2$ , have to be "S-units." In plain English, this means their prime factors can only come from a very small, specific list of numbers (the primes that divide the alphabet size and the number 2).

Here is the clever part: Bennett showed that for a perfect code to exist, these two numbers $r_1$ and $r_2$ would have to be incredibly close together—so close that their difference is tiny compared to their size. However, a famous branch of mathematics called Diophantine approximation (which studies how well you can approximate numbers with fractions) tells us that numbers with restricted prime factors usually can't get that close to each other unless they are very small.

Bennett combined this with a specific equation derived from the geometry of the problem:
$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$
This equation is the "smoking gun." It links the alphabet size $q$ directly to the distance between the two roots.

The Big Reveal

Using this equation and powerful tools from number theory, Bennett proved a series of "impossibility" results:

The "Small Prime" Ban: If the largest prime factor of your alphabet size is 13 or smaller, a perfect 2-code is impossible. He did this by listing all the possible pairs of numbers that could be the roots and showing that none of them fit the equation.
The "Huge Number" Barrier: For the general case where the alphabet is $2^\alpha \times p^\beta$ , he proved that if a code did exist, the prime $p$ would have to be larger than $10^{10}$ (ten billion). Even more restrictively, the power of 2 ( $\alpha$ ) would have to be greater than 20.
The "Mod 8" Rule: If such a code existed, the prime $p$ would have to be a number that leaves a remainder of 3 when divided by 8 (like 3, 11, 19, etc.).

The paper essentially says: "We have checked the small numbers, and they don't work. For the big numbers, the math says they would have to be so enormous and follow such strict rules that they effectively don't exist in any practical sense."

The Schröder-Hipparchus Surprise

One of the most delightful parts of the paper is how it uses a sequence of numbers from classical combinatorics called Schröder-Hipparchus numbers (also known as super-Catalan numbers). These numbers, which usually appear in problems about counting ways to arrange parentheses or paths on a grid, suddenly show up in the middle of the error-correcting code proof.

Bennett used these numbers to expand a complex equation into a series of terms. It's like finding a hidden pattern in a chaotic noise. By expanding the equation using these numbers, he could show that the terms grow too fast to allow the "close proximity" required for a perfect code to exist, unless the numbers involved are absurdly large.

The Final Verdict

So, what is the bottom line? The paper confirms a long-held suspicion in the mathematical community: Perfect 2-codes over arbitrary alphabets likely do not exist.

While the paper doesn't claim to have found the one perfect code that might be hiding in the universe (because it proves that if one exists, it must be larger than $10^{10}$ and follow impossible constraints), it effectively rules out the vast majority of cases. It closes the door on alphabet sizes like 10, 15, 21, and many others, and pushes the possibility of a solution so far into the realm of giant numbers that it is considered practically non-existent.

The author's work is a triumph of "negative" proof. Instead of finding a treasure, he proved that the treasure chest is empty, or at least that the key to opening it requires a lock that hasn't been invented yet. For anyone trying to build error-correcting codes for these specific alphabet sizes, the message is clear: stop looking for a perfect 2-code; it's not there.

Technical Summary: Perfect 2-Codes Over Arbitrary Alphabets

Problem Statement
The paper addresses the classification of perfect $e$ -codes over an alphabet of size $q$ . While the classification for $e \ge 3$ is complete (establishing that only the Golay codes exist when $q$ is a prime power, and no such codes exist when $q$ is not a prime power), the case of $e=2$ with non-prime-power alphabet sizes remains largely open. Specifically, it is conjectured that no perfect 2-codes exist for any $q$ that is not a prime power. Previous results had resolved specific cases (e.g., $q=2^\alpha 3^\beta$ , or specific small composite values), but a general proof for arbitrary composite $q$ was lacking. The primary objective of this work is to confirm this conjecture for a broad class of alphabet sizes, specifically those of the form $q = 2^\alpha p^\beta$ (where $p$ is prime) and more generally for $q$ with bounded prime factors.

Methodology
The author employs a synthesis of combinatorial coding theory and advanced Diophantine approximation techniques. The approach proceeds through the following logical steps:

Algebraic Formulation: The existence of a perfect 2-code implies the existence of two distinct integer roots, $r_1$ and $r_2$ , for a specific polynomial derived from Lloyd's theorem. These roots satisfy the sphere packing bound and are $S$ -units, where $S$ is the set of primes dividing $2q$ .
Fundamental Equation: A critical identity, $q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$ , is derived. This equation implies that the roots $r_1$ and $r_2$ must be unusually close to one another relative to their magnitude.
Diophantine Analysis: The problem is reduced to bounding the difference between $S$ $S$ -units. The paper utilizes:
- Linear Forms in Logarithms: Bounds for linear forms in complex logarithms (specifically results by Tijdeman, Matveev, and Laurent) are used to establish lower bounds on the difference $|r_2 - r_1|$ .
- Ridout's Theorem: A $p$ -adic version of Roth's theorem is applied to limit the solutions of specific polynomial-exponential equations.
- Continued Fractions: For the case $q = 2^\alpha p^\beta$ , the ratio $\log p / \log 2$ is analyzed via its continued fraction expansion to bound the exponents involved.
- Combinatorial Identities: The Schröder-Hipparchus numbers (super-Catalan numbers) appear unexpectedly in the expansion of powers of $p$ within the congruence relations derived from the code parameters.
Computational Verification: For specific ranges of parameters (e.g., small primes $p$ or small exponents $\alpha$ ), the theoretical bounds are combined with extensive computational checks using Hensel lifting and modular arithmetic to rule out the existence of solutions.

Key Contributions and Results

Theorem 2 (Main Result for $q = 2^\alpha p^\beta$ ): The paper proves that there are at most finitely many perfect 2-codes on $q$ symbols where $q = 2^\alpha p^\beta$ ( $p$ prime, $\alpha, \beta \in \mathbb{Z}^+$ ). Furthermore, if such a code were to exist, it would necessitate extremely large parameters: $\alpha > 20$ , $\beta \le 2519$ , $p > 10^{10}$ , and $p \equiv 3 \pmod 8$ . The proof effectively eliminates all cases where $\alpha \le 20$ through computational arguments and handles $\alpha > 20$ via ineffective bounds derived from Ridout's theorem.
Theorem 3 & 4 (Bounded Prime Factors): The author strengthens Reuvers' theorem by showing that for any fixed integer $P_0$ , there are at most finitely many perfect 2-codes where the greatest prime factor of $q$ , denoted $P(q)$ , satisfies $P(q) \le P_0$ . Specifically, Theorem 4 provides an explicit proof that no perfect 2-codes exist for any $q$ with $P(q) \le 13$ .
Theorem 5 (Generalization): A qualitative (but ineffective) result is established for $q = q_0 p^\alpha$ , where $P(q_0) \le P_0$ . This generalizes the previous theorems to a wider class of alphabet sizes, confirming finiteness under these constraints.

Significance and Claims
The paper claims to significantly advance the classification of perfect codes by resolving the $e=2$ case for a wide variety of non-prime-power alphabet sizes, a problem that had seen little progress since the early 1980s. The author notes that the methods employed are "significantly more computationally efficient" than previous approaches that relied on finding integral points on Mordell curves.

The work confirms the conjecture that no perfect 2-codes exist for $q = 2^\alpha p^\beta$ in all cases where $\alpha \le 20$ , and reduces the remaining open cases to parameters so large ( $p > 10^{10}$ ) that their existence is effectively ruled out for practical purposes, though the proof for $\alpha > 20$ remains ineffective. The paper does not claim to have proven the non-existence for all arbitrary $q$ , but rather establishes finiteness and explicit non-existence for the most significant families of composite alphabet sizes. The results rely heavily on the interplay between the structural constraints of perfect codes and deep theorems in Diophantine approximation.

The Story of the Impossible Puzzle

The Mathematical Detective Work

The Big Reveal

The Schröder-Hipparchus Surprise

The Final Verdict

More like this