2
$\begingroup$

I'm given the task to prove that a (perfect) $(90, 2^{78}, 5)_2$ code $\mathscr C$ doesn't exist. To reach this goal, I'm also given an outline on what to do, but so far, I'm a bit lost on what to do.

Let's assume that such a code $\mathscr C$ would exist.

First, I'm asked on why we can assume without loss of generality that $0 \in \mathscr C$ (where $0$ denotes the vector, consisting of just $0$'s). Next, I'm asked to find a recursive formula for the weight distribution $(A_i)_{0 ≤ 1 ≤ n}$ of $\mathscr C$. Finally, I shall set $A_0 = 1$ (because w.l.o.g. $c \in \mathscr C$) and calculate $A_i$ for $1 ≤ i ≤ 7$ via that formula, and then deduce some conclusions about the (non-)existence of $\mathscr C$.

Now I'm already a bit lost on the first statement. I thought that maybe we could use equivalence of codes here to somehow get from any code that satisfies the parameters to one that contains the $0$? I'm not sure about the details though on how to deduce that from equivalence. I'm also a bit confused about whether or not $\mathscr C$ is linear (or can be assumed to be, without loss of generality). Does the existence of any code with these parameters imply the existence of a linear code with these parameters? Because as a linear code, it would automatically contain the $0$.

So, well let's say we know that $0 \in \mathscr C$; then the big elephant in the room for me would be finding this recursive formula – I suspect that, once such a formula is found, the rest would just be straightforward calculation that would lead to results that contradict the parameters of the code, or something.

I already know that for any binary linear code $\mathscr D$ with $d(\mathscr D) ≥ 3$ and weight distribution $(B_i)$, there are at least $i B_i$ vecotrs $a \in \mathbb F_q^n$ with $wt(a) = i-1$ aswell as $\min_{c \in \mathcal D} d(a, c) = 1$, aswell as $(n-i) B_i$ vectors $b \in \mathbb F_2^n$ with $wt(b) = i+1$ and $\min_{c \in \mathcal D} d(b, c) = 1$ (both facts are basically a simple counting argument). We once used that in my class to deduce a recursive formula for binary Hamming codes, so maybe it's somewhat helpful here? I'm not really sure though. I'm really just helpless at this point on how to get that recursive formula because I don't know at all what it shall look like.

If there's another clever proof that such a code $\mathscr C$ doesn't exist that doesn't follow these steps, then I'm open to that aswell.

$\endgroup$

1 Answer 1

2
$\begingroup$

We've assumed $0 \in \mathscr C$, then $A_0=1$

We know that $d_{min} =5$, then $A_1=A_2 = A_3 = A_4=0$

Let's think about $w=5$ ($A_5$). Because we are assuming the code is perfect, each tuple belongs to a "ball" (with center in a codeword) with radius $t=2$. Then the tuples with weight $5$ can be grouped according to to the distance to its nearest codeword. Then we get

$$ {n\choose 5}=A_5+A_4 {n-4 \choose 1} + A_6 {6 \choose 1} +\\ +A_3 {n-3 \choose 2} + A_7 {7 \choose 2} + A_5 {5 \choose 1}{n-5 \choose 1} \tag{1}$$ Or $$43949268= 426 A_5 + 6 A_6 + 28 A_7$$

The recursion $(1)$ can also be written for other values of $w$. In particular, if we write it for $w=3$, it should allow us to compute $A_5$ and so on.

BTW: notice that I didn't need to assume that the code is linear.


Update Explanation of $(1)$

There are ${n \choose 5}$ a total of tuples of weight $5$. Each one of these must belong to one and only one ball, at a distance up to 2 from a codeword. We group these by this distance. At distance $0$ there are precisely $A_5$ tuples.

At distance 1 we have two cases: around each codeword of weight $4$ we have $n-4$ tuples (changing a $0 \to 1$) and around each codeword of weight $6$ we have $6$ tuples (changing a $1 \to 0$).

At distance 2 we have to count three cases:

$A_3$: $0 \to 1$, $0 \to 1$

$A_7$: $1 \to 0$, $1 \to 0$

$A_5$: $1 \to 0$, $0 \to 1$

Regarding your doubt about why the assumption $0 \in \mathscr C$ does not lose generality:

Say we have code (not necessarily linear) $\mathscr C_1$ . If we build a new code $\mathscr C_2$ by summing some fixed vector $x$ to all codewords of the original, then the distances don't change - then $\mathscr C_2 $ is perfect iff
$\mathscr C_1 $ is perfect. Hence, if we had a perfect code without the cero codeword, we could construct another perfect code with cero by adding some codeword to all of them.

$\endgroup$
2
  • $\begingroup$ Thanks! I've got two questions though. First, could you go into a little more detail on how you actually derive the formula? I understand that there are $\pmatrix{n \\ 5}$ words of weight $5$ in $\mathbb F_2^n$, I just can't fully see yet how we get the binomial coefficients on the RHS when we group them all together. And the 2nd question is, well, about the assumption... why can we assume that $0 \in \mathscr C$; or in other words, why does the existence of a code with these parameters imply the existence of a code with these parameters that contains $0$? $\endgroup$
    – moran
    Commented Nov 20, 2016 at 21:04
  • $\begingroup$ Ah, that makes sense; thanks again for taking the effort and answering both of my remaining questions. I haven't done the calculation yet but I think it will be straightforward to show now with this formula that such a code doesn't exist. $\endgroup$
    – moran
    Commented Nov 20, 2016 at 21:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .