🔢 mathematics

A counterexample to the Etzion-Silberstein conjecture

This paper disproves the Etzion-Silberstein conjecture by proving that the Singleton-type upper bound for linear Ferrers-diagram rank-metric codes is not always attainable, specifically demonstrating that a binary code on a specific Ferrers diagram with minimum rank distance 3 has a maximum dimension of 11 rather than the conjectured 12.

Original authors: Jitendra Prajapati

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jitendra Prajapati

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 efficient storage system possible using a grid of light switches. In the world of digital communication, these grids are called "codes," and they are the invisible guardians that keep your text messages, photos, and videos from getting scrambled when they travel across the internet. The goal is always the same: pack as much information as possible into the grid while ensuring that even if some switches get flipped by accident (noise), you can still figure out what the original message was.

For decades, mathematicians have been trying to solve a specific puzzle about how to arrange these switches in a "Ferrers diagram"—a shape that looks like a staircase or a pyramid of blocks. They discovered a theoretical "speed limit" for how much information could fit into any given staircase shape without losing the ability to fix errors. This limit is called the Singleton bound. In 2009, two brilliant mathematicians, Etzion and Silberstein, made a bold guess: they believed that for every possible staircase shape and every type of error-correcting rule, you could always build a perfect code that hits this speed limit exactly. It was like saying, "No matter what shape the storage box is, we can always fill it to the very brim without spilling a drop." This idea became a famous conjecture, a guiding star for researchers trying to design better error-correcting codes.

Now, a new paper by Jitendra Prajapati has come along and gently, but firmly, turned that star off. The author proves that the Etzion–Silberstein conjecture is actually false. Using a specific, oddly shaped staircase made of blocks, the paper shows that you simply cannot fill it to the theoretical brim. Instead of the predicted maximum of 12 units of information, the best you can do is 11. It's a bit like trying to pack a suitcase that looks like it should hold 12 shirts; you might think it's full, but if you try to shove in that 12th shirt, the zipper won't close, or the fabric will rip. The paper doesn't just guess this; it uses a massive, computer-verified mathematical proof to show that no matter how you try to arrange the switches, a 12th unit is mathematically impossible for this specific shape.

The story begins with a diagram called $E$ , which looks like a staircase with four tall columns of five blocks each, followed by two short columns of just one block. The rules of the game require that any "message" (a pattern of switches) you write on this diagram must be strong enough to survive a certain amount of damage, specifically a "minimum rank distance" of 3. Think of this as a requirement that every message must be complex enough that you have to change at least three different parts of it to turn it into a different valid message. Based on the old theory, the math said you should be able to fit 12 independent messages into this shape.

However, the author dug deep into the structure of these codes and found a hidden trap. To prove the limit is lower, the paper breaks the problem down into a "kernel-lift" puzzle. Imagine you have a giant, complex machine (the code) and you try to shrink it down to its core engine (a smaller code). The paper shows that if a perfect 12-message code existed, it would have to be built on top of a very specific type of engine called an MRD code. There are only three known types of these engines. The author then ran a massive, exhaustive search—checking over 8 million possible variations of how the pieces could fit together—to see if any of them could support that 12th message.

The result was a resounding "no." The computer checked every single possibility, and in every case, the math broke down. The "engine" couldn't support the weight of the 12th message without violating the rules of the game. The paper explicitly rules out the existence of a 12-dimensional code for this shape. Instead, the author constructs a working example of a code with 11 messages, proving that 11 is the true maximum. This isn't a simulation or a guess; it is a rigorous, step-by-step proof that has been double-checked by independent software verifiers.

The paper doesn't stop there. It also discovers a clever trick called "row-cone propagation." Imagine taking your failed 12-block staircase and adding a new layer on top, then adding a few more blocks to the side. The paper shows that if you can't fill the original shape perfectly, you can't fill these new, larger shapes perfectly either. This means the failure isn't just a one-time fluke; it happens at every level of complexity. For any minimum distance of 3 or higher, there is a staircase shape where the theoretical limit is 12, but the actual limit is stuck at 11.

In the end, this paper is a significant correction to the map of mathematical knowledge. It tells us that while the Etzion–Silberstein bound is a great guide, it isn't a law of nature that holds true for every single shape. The "perfect packing" isn't always possible. The author provides the exact blueprint for the best possible code (dimension 11) and proves that the dream of dimension 12 is mathematically impossible for these specific diagrams. It's a reminder that in the world of abstract math, even the most elegant guesses can have exceptions, and sometimes, the truth is just one block shy of what we hoped for.

Technical Summary: A Counterexample to the Etzion–Silberstein Conjecture

Problem Statement
The Etzion–Silberstein conjecture posits that for any Ferrers diagram $D$ , any minimum rank distance $d$ , and any finite field $\mathbb{F}_q$ , the Singleton-type upper bound on the dimension of linear Ferrers-diagram rank-metric codes is attainable. Specifically, it asserts that there exists a code of dimension $k = \nu_{\min}(D, d)$ , where $\nu_{\min}$ is a combinatorial bound derived from the diagram's geometry. While the bound has been proven attainable for substantial families of diagrams, the conjecture remained open in the general case, particularly over small fields.

Methodology
The author disproves the conjecture by constructing a specific counterexample over the binary field $\mathbb{F}_2$ . The approach combines combinatorial reduction, classification of Maximum Rank Distance (MRD) codes, and exhaustive computational verification.

Counterexample Selection: The author focuses on the Ferrers diagram $E$ with column heights $(5, 5, 5, 5, 1, 1)$ and minimum rank distance $d=3$ . The Etzion–Silberstein bound predicts a dimension of 12.
Reduction to Kernel-Lift Problem: The existence of a binary $[E, 12, 3]$ code is reduced to the existence of a specific structure within a binary $[4 \times 4, 12, 2]$ MRD code. Specifically, a code of dimension 12 exists if and only if there is a codimension-two subspace $K$ within an MRD code $U$ and a linear map $R: K \to \mathbb{F}_2^4$ such that for every rank-two matrix $M \in K$ , the vector $R(M)$ is not contained in the row space of $M$ .
Classification of MRD Codes: The proof relies on the classification of binary $[4 \times 4, 4, 4]$ spread codes (the orthogonal complements of the required MRD codes). There are exactly three equivalence classes of such codes.
Exhaustive Elimination:
- The author enumerates all possible codimension-two subspaces (kernels) $K$ within each of the three MRD classes. The total search space comprises 8,382,465 kernels.
- A "rank-two filter" (Lemma 4) is applied, which proves that any valid kernel must contain exactly 105 rank-two matrices. This filter eliminates two of the three equivalence classes entirely and reduces the search in the remaining class to four specific kernel orbits.
- For the four surviving orbits, the constraint system (requiring $R(M) \notin \text{row}(M)$ for all rank-two $M$ ) is encoded as a set of affine parity equations.
Verification: The resulting constraint systems are proven unsatisfiable using independent SAT solvers (CaDiCaL and CryptoMiniSat) and custom verifiers. The verification includes a raw enumeration of all kernels without orbit reduction to ensure reproducibility.

Key Results

Upper Bound: The author proves that any binary linear code supported on $E$ with minimum rank distance 3 has a dimension of at most 11.
Lower Bound: An explicit binary linear code of dimension 11 supported on $E$ with minimum rank distance 3 is constructed.
Disproof: Since the optimum dimension is 11 while the Etzion–Silberstein bound is 12, the conjecture is false for the pair $(E, 3)$ over $\mathbb{F}_2$ .
Propagation: Using a "row-cone propagation" identity, the author demonstrates that this counterexample can be extended to generate counterexamples for every minimum rank distance $d \geq 3$ . Specifically, for every $d \geq 3$ , there exists a Ferrers diagram where the bound predicts 12, but the optimum is 11.
Minimality: The diagram $E$ (corresponding to $n=6$ in the irreducible family $E_n$ ) is identified as the smallest failing instance; smaller diagrams in the family attain their bounds over $\mathbb{F}_2$ .

Significance and Claims
The paper establishes that the Etzion–Silberstein conjecture does not hold universally, even over the smallest finite field. The author claims that their result resolves the conjecture in the negative and identifies the failure of the related puncturing–inclusion MRD conjecture for the instance $(n, d, \mathbb{F}) = (5, 3, \mathbb{F}_2)$ .

The work emphasizes computational rigor and reproducibility. The proof is described as "finite, exact, and independently reproducible," relying on exact binary arithmetic rather than floating-point approximations. The author provides a complete verification package, including explicit code constructions, solver logs, and cryptographic hashes of the data, allowing independent researchers to verify the non-existence of the dimension-12 code. The result reduces the general conjecture to irreducible families, showing that even within these fundamental structures, the Singleton-type bound is not always attainable.

Technical Summary: A Counterexample to the Etzion–Silberstein Conjecture

More like this