perfect binary e-error correcting code

Question

let C be a perfect binary e-error correcting code of length n.

assume 0 is a symbol and that 0 vector is a codeword.show that P={1,2,...,n}

together with supports of codewords of weight 2e+1form an STS(e+1,2e+1,n)

thanks for your help...

Answer 1

Let $d = 2e + 1$ be the minimum distance of $C$. For all $v\in\{0,1\}^n$, we have $w_{\text{Ham}}(v) = \left|\operatorname{supp}(v)\right|$ and $d_{\text{Ham}}(v,v') = \left|\operatorname{supp}(v) \triangle \operatorname{supp}(v')\right|$, where $\triangle$ denotes the symmetric difference of sets. In the following, we identify a vector $v\in \{0,1\}$ with its support $\operatorname{supp}(v)\subseteq P$.

We are going to show that the set of codewords of weight $d$ form a Steiner system $S(e+1,d,n)$. Thus, we have to show that for any subset $T$ of $P = \{1,\ldots,n\}$ of size $\left|T\right| = e+1$, there is a unique codeword $K$ of size $\left|K\right| = d$ containing $T$.

1. There is at most one such codeword: If there were two distinct codewords $K_1$, $K_2$ of weight $d$ such that $T \subset K_1$, $T \subset K_2$, then the Hamming distance of $K_1$ and $K_2$ was $$\left| K_1\triangle K_2\right| = \left| K_1\setminus (K_1 \cap K_2)\right| + \left| K_2\setminus (K_1 \cap K_2)\right|\\\leq 2(d - (e+1)) = 2d - (2e + 2) = d-1,$$ contradicting the minimum distance of the code.

2. There is at least one such codeword: Since $C$ is perfect, there is a codeword $K$ such that the Hamming ball with center $K$ and radius $e$ contains $T$. By the triangular inequality, $\left|K\right|\leq \left| T\right| + e = 2e + 1 = d$. On the other hand, since $C$ contains the zero word and its minimum distance is $d$, $\left|K\right| \geq d$. So $\left|K\right| = d = 2e + 1$, and the distance of $T$ and $K$ is at most $e$. By $\left|T\right| = e+1$, this implies that the distance is exactly $e$ and $T\subset K$.