# coding theory- perfect codes

I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows:

You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$.

I have been using the fact that $C$ is a perfect code so it attains the Hamming bound then saying that it is less than the Hamming bound for $D$, but you get an inequality involving a binomial sum on both sides, which is really messy. I'm not really sure what other properties I can use to work this out. Any help would be really appreciated, thanks

• What function is $d$? – G. Bach Nov 6 '15 at 13:55
• @G.Bach Minimal distance. – Yuval Filmus Nov 6 '15 at 14:02
• Start with the definition of $C$. It practically states that this property holds. – Ran G. Nov 6 '15 at 14:07
• @RanG. how? using the fact that $C$ is perfect? – shex95 Nov 6 '15 at 14:54
• Yes. Maybe add to the question the definition of "perfect code" you are using (I saw several equivalent definitions; one of them was actually almost the statement of your question verbatim). – Ran G. Nov 6 '15 at 16:16

According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w_0$."

OK, but this is cheating.

A code $C$ is perfect if it attains the Hamming bound
what is this Hamming bound? Basically, it's a counting argument. If you have a word $w\in F^n_q$, how many words are there with in $F^n_q$ whose distance from $w$ is at most $e$? If you do the counting, you will get there are exactly $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ such words. [Why? If the distance is $i$, choose $i$ indices (out of the $n$ possible indices), each such index can get any of the $q-1$ different values from $w$ in that index.] The bound then says that if we split the universe into disjoint "balls" where each ball contains a center $w$ and all the $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ words within distance $e$ from $w$, we will have at most $$\frac{|F^n_q|}{size(ball)} = \frac{q^n}{\sum_{i=0}^e \binom{n}{i} (q-1)^i}$$ such (disjoint) balls.
A code that attains the Hamming bound means that any word is within distance $e$ of some codeword. That is, if you think on each codeword in $C$ as a center of a ball with radius $e$, then the codewords cover the entire universe: no word in $F^n_q$ is left outside some ball. Note that the distance of this code is $2e+1$: two codewords belong to two different "balls", and each ball is of radius $e$ (in Hamming distance).
But if the entire space is covered with balls, it means that any word is within distance $e$ of some codeword. This is exactly the first definition I wrote in this post. Thus, if you take any other word and make it a codeword, this word already belongs to some ball, so it is within distance $e$ from the center of that ball, and the new code cannot have a minimal distance greater than $e$.