Binary $[31,22,5]$ code does not exist

Question

Consider a binary $[31,22,5]$ linear code. There are $2^{31-22}=2^9$ cosets and we have $t=\frac{5-1}{2}=2$.

I am looking to find a contradiction, by considering the number of coset leaders with weights $0,1$ and $2$, and considering, for each coset, an upper bound for the number of words of weight $3$ contained in it.

Any help on finding this two values? Thanks in advance!

Answer 1

There are $\binom{31}{0}+\binom{31}{1}+\binom{31}{2}=497$ of weight equal to or less than $2$. So, we have $2^9-497=15$ cosets of weight greater than $2$. In cosets of weight $2$ there are, at most, $\lfloor{\frac{29}{3}}\rfloor\times\binom{31}{2}=4185$ vectors with weight $3$.

This way, there are $\binom{31}{3}-4185=310$ vectors of weight $3$ that are not in cosets of weight $2$.

Suppose there is a coset of weight $3$, then it has, at most, $\lfloor{\frac{31}{3}}\rfloor=10$ vectors of weight $3$. But it is not possible to distribute $310$ vectors of weight $3$ over $15$ cosets, kowing that each coset has, at most, $10$ vectors of weight $3$. The cases where a coset with weight greater than $4$ would be even worse.

There is no binary [31,22,5] linear code.

Answer 2

You say you want to count the weight 3 codewords in each coset; $\mathcal{C}$ contains no weight 3 codeword, and also no weight 1 coset can contain a weight 3 word (I leave it to you to show this).

For a weight 2 coset of the form $u + \mathcal{C}$ with $\mathrm{wt}(u) = 2$, the only way to get a weight 3 word is from a $c \in \mathcal{C}$ with $\mathrm{wt}(c) =5$ and $\mathrm{wt}(u \cap c) = 2$. So if $\{i,j\}$ are the coordinates where $u_{i}=u_{j}=1$, you want to consider how many weight 5 codewords $c$ there can possibly be with $c_{i}=c_{j}=1$, all at distance at least 5 apart. To count these, notice that these codewords cannot be at distance exactly 5, the distance between them must be even since they have the same weight.