Easy ways to prove that a binary $[9,3,5]$ linear code can't exist

Question

I've tried to solve an exercise that goes like this:

Prove that a $[9,3,d]$ linear binary code that corrects 2 mistakes doesn't exist.

To prove this, first I've determined that $d=5$ is the most restrictive case. Then, I've tried to use Hamming's, Singleton's and Plotkin's bounds in order to easily see if said code can't exist but I haven't been able to prove anything with the bounds.

Another thing I've tried is to use the fact that $d-1$ is the largest number of linearly independent columns in the control matrix. This way, I've proved that said code cannot exist by analizing the different combinations of vectors to put in each column.

However, this has taken such a long time and I was wondering wether there was a time efficient way to solve this kind of exercises.

Thanks in advance

Answer 1

The Griesmer bound tells us that if we have a $3$-dimensional binary linear code with minimum distance $d\ge5$, its length $n$ satisfies the inequality $$n\ge 5+\lceil\frac52\rceil+\lceil\frac54\rceil=5+3+2=10.$$

My experience is that the Griesmer bound works well for relatively low-dimensional codes, which is what we have here.

Answer 2

For binary codes, the extension by a parity check bit gives that the existence of a $[n,k,d]$-code with odd $d$ is equivalent to the existence of a $[n+1,k,d+1]$ code.

Plotkin should better be applied to the even $d$ variant. (For Hamming, use odd $d$. For Griesmer, use even $d$. For Singleton, it does not matter.)

In our case, Plotkin readily shows that there is no $[10,3,6]$ code. Hence there is no $[9,3,5]$ code.

It is interesting to notice, that ­– as you mentioned – the direct application of Plotkin to $[9,3,5]$ does not give a contradiction.

Another remark: This argumentation also shows that there is no non-linear $(9,2^3,5)$-code. The Griesmer bound only excludes linear $[9,3,5]$ codes.