🔢 mathematics

Counterexamples to Charpin's Conjecture on BCH codes

This paper disproves Charpin's conjecture by constructing an infinite family of primitive narrow-sense BCH codes whose minimum distance strictly exceeds their Bose distance, with the gap growing at least as the cube root of the code length for binary codes.

Original authors: Run Zheng, Yaoran Yang, Yutong Zhang, Maosheng Xiong

Published 2026-08-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Run Zheng, Yaoran Yang, Yutong Zhang, Maosheng Xiong

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 radio channel, like shouting a recipe to a friend in a hurricane. To make sure the message arrives correctly even if some words get blown away or garbled, you add extra "safety words" to your message. In the world of digital communication, these safety nets are called error-correcting codes. One of the most famous and powerful families of these codes is called BCH codes (named after their inventors). They are the unsung heroes behind everything from your smartphone's data storage to deep-space satellite transmissions.

The big question that has kept mathematicians and engineers up at night for decades is: just how good are these codes at fixing errors? To measure this, we look at the "minimum distance," which is essentially the smallest number of errors the code can guarantee to catch and fix. There is a well-known rule of thumb, called the "Bose distance," that gives a safe, conservative estimate of this number. For a long time, experts believed that the true power of these codes was never much better than this safe estimate. They thought the gap between the "safe guess" and the "real power" was tiny and predictable, like a car that never drives more than four miles per hour faster than its speedometer says. This belief was so strong that it became a famous guess, or "conjecture," named after a researcher named Charpin. If this guess were true, it would mean we could easily predict exactly how well these codes work just by doing some simple counting.

But what if that guess is wrong? What if, under the right conditions, these codes are actually supercharged, capable of fixing way more errors than anyone thought possible? That is exactly what a team of researchers has just discovered. They didn't just find a tiny exception; they found a whole new family of these codes that breaks the rules completely. They proved that the gap between the "safe guess" and the "real power" isn't just a little bit bigger—it can be huge, growing larger and larger as the codes get bigger. In fact, for certain codes, the real power is so much greater than the guess that the old rule of thumb falls apart entirely. This isn't just a small correction; it's a fundamental shift in our understanding of how these digital safety nets work, showing that nature has more tricks up its sleeve than we previously imagined.

The Big Discovery: Breaking the "Four-Error" Rule

In this paper, the authors, Run Zheng, Yaoran Yang, Yutong Zhang, and Maosheng Xiong, set out to test the limits of these BCH codes. Their main goal was to see if Charpin's conjecture—that the gap between the estimated distance and the real distance is always small (specifically, no more than 4 for binary codes)—was actually true.

To understand their method, imagine the BCH codes as a fortress. The "Bose distance" is like the height of the outer wall that everyone agrees on. The "minimum distance" is the actual height of the strongest point in the fortress. For years, people assumed the strongest point was never more than a few feet higher than the agreed-upon wall. The authors, however, decided to look for a hidden, secret entrance to a much taller tower inside the fortress.

They used a clever mathematical trick involving something called "Generalized Reed-Muller codes." Think of these as a different kind of code that has very strict rules about the "weight" (or size) of its messages. The authors showed that their specific BCH codes are actually hiding inside these stricter codes. Because of the strict rules of the "parent" code, the messages in the BCH code are forced to be much heavier (meaning they can handle more errors) than the standard wall height suggested.

The result? They constructed an infinite family of codes where the real minimum distance is strictly greater than the Bose distance. In fact, they proved that for a specific set of parameters (where the code length is related to a number $m$ that is at least 10 and not equal to 12), the gap isn't just a tiny number like 4. It grows significantly as the code gets longer.

For example, if you take a binary code (the kind used in most computers) with a length related to $m=13$ (which means the code has a length of 8191), the gap between the estimated distance and the real distance is $2^{\lfloor(13-1)/3\rfloor-1}$ . This calculates to a gap of 8, which is already double the limit Charpin's conjecture allowed. But as you make the codes bigger (increasing $m$ ), this gap doesn't just stay at 8; it expands rapidly. It grows as the cube root of the code length, meaning for very large codes, the real power is vastly superior to the old estimates.

Why Was This Hidden for So Long?

You might wonder, "If this is such a big deal, why didn't anyone find it sooner?" The authors explain that the smallest counterexample they found requires a code length of 8191. Previous computer searches that helped form the conjecture only checked codes up to a length of 511. It's like looking for a giant elephant in a room full of mice; if you only look at the mice, you'll never see the elephant. The phenomenon they discovered is simply too large to have been spotted by the earlier, smaller-scale experiments.

The Bottom Line

This paper definitively disproves Charpin's conjecture. It shows that the minimum distance of primitive narrow-sense BCH codes is not bounded by a small, fixed number above the Bose distance. Instead, the gap can be arbitrarily large, growing as the code gets longer.

The authors didn't just guess this; they provided a rigorous mathematical proof. They constructed the codes, calculated the exact distances, and showed that the gap is real and significant. For binary codes, they even proved that the gap is exactly equal to their formula, leaving no room for doubt.

This discovery changes the landscape of coding theory. It tells us that we cannot rely on simple, fixed bounds to predict the performance of these codes. Instead, we must dig deeper and look for these hidden "towers" within the codes, because the true error-correcting power of these digital guardians is far more impressive than we ever dared to hope.

Technical Summary: Counterexamples to Charpin's Conjecture on BCH Codes

Problem Statement
Determining the exact minimum distance ( $d$ ) of Bose–Chaudhuri–Hocquenghem (BCH) codes remains a fundamental and unresolved challenge in coding theory. While the Bose distance ( $d_B$ )—defined as the largest designed distance that generates a specific code—provides a sharp lower bound via the BCH bound ( $d \ge d_B$ ), the exact value of $d$ is generally unknown.

Charpin conjectured that for binary primitive narrow-sense BCH codes, the gap between the true minimum distance and the Bose distance is bounded by a small absolute constant. Specifically, it was conjectured that for any integer $\delta$ in the valid range, $d(C(2,m,\delta)) \le d_B(C(2,m,\delta)) + 4$ . This conjecture, if true, would reduce the problem of determining minimum distance to a combinatorial problem regarding $q$ -cyclotomic coset leaders. Despite extensive numerical verification for code lengths up to 511, no proof or counterexample had been reported for narrow-sense BCH codes.

Methodology
The authors disprove Charpin's conjecture by constructing an infinite family of primitive narrow-sense BCH codes where the minimum distance strictly exceeds the Bose distance by a significant margin. The core methodology involves:

Embedding in Generalized Reed–Muller (GRM) Codes: The authors identify specific BCH codes as subcodes of punctured generalized Reed–Muller codes ( $PGRM_q(\ell, m)$ ). This is achieved by analyzing the defining sets of the codes.
Weight Divisibility Constraints: By leveraging Ax's theorem on the number of zeros of polynomials over finite fields, the authors establish that codewords in the containing GRM codes must satisfy specific weight divisibility conditions. Specifically, the weights of codewords in $GRM_q(\ell, m)$ are divisible by $q^{\lfloor (m-1)/\ell \rfloor}$ .
Gap Forcing: The divisibility constraints forbid codeword weights within a specific interval immediately above the designed distance. This forces the minimum distance of the BCH subcode to jump to the next allowable weight, creating a gap between $d$ and $d_B$ .
Coset Leader Analysis: The authors rigorously prove that for their constructed parameters, the designed distance $\delta$ is indeed a coset leader, ensuring that the Bose distance $d_B$ is exactly $\delta$ .

Key Contributions and Results
The paper presents the following main result (Theorem 1):

Construction: Let $q$ be a prime power, $m \ge 10$ with $m \neq 12$ . Define $u = \lfloor m/4 \rfloor$ and $t = \lfloor (m-1)/3 \rfloor$ . For any integer $s$ such that $u \le s < t$ , let the designed distance be:
$\delta = q^m - q^{m-1} - q^{m-1-u} - q^s - 1$
Bose Distance: The primitive narrow-sense BCH code $C(q,m,\delta)$ has a Bose distance exactly equal to $\delta$ ( $d_B = \delta$ ).
Minimum Distance: The minimum distance satisfies $d \ge \delta + q^s$ .
Binary Case Equality: For the binary case ( $q=2$ ), the minimum distance is exactly $d = \delta + 2^s$ .

Disproof of Charpin's Conjecture
By setting $s = t - 1$ in the binary case, the authors derive a subfamily of codes where the gap between the minimum distance and the Bose distance is:
$d - d_B = 2^{\lfloor (m-1)/3 \rfloor - 1}$
This gap:

Strictly exceeds 4 for all $m \ge 13$ .
Grows exponentially with $m$ (or as the cube root of the code length $n$ ).
Directly contradicts Charpin's conjecture that the gap is bounded by 4.

The smallest counterexample occurs at $m=13$ (code length 8191), which explains why the conjecture remained unchallenged by previous numerical computations limited to lengths up to 511.

Significance
The paper demonstrates that the gap between the minimum distance and the Bose distance for primitive narrow-sense BCH codes is not merely small but can be arbitrarily large, growing as a fixed power of the code length. This result invalidates the expectation that $d$ and $d_B$ are closely related by a constant bound. Consequently, determining the exact minimum distance of BCH codes cannot be reduced solely to combinatorial properties of coset leaders; the structural properties of the codes (specifically their relationship to Reed–Muller codes and weight divisibility) play a critical role. The authors note that while they have established a lower bound for the gap, the exact maximum possible value of $d - d_B$ for a given length remains an open question.

The Big Discovery: Breaking the "Four-Error" Rule

Why Was This Hidden for So Long?

The Bottom Line

Technical Summary: Counterexamples to Charpin's Conjecture on BCH Codes

More like this