# Thread: q-ary code proof using spheres

1. ## q-ary code proof using spheres

Show that there is no q-ary code of length 5 and distance 3 with more than $\frac{q^5}{5q-4}$ codewords. You should prove this from first principles using spheres and without using known bounds on the number of codewords.

This is my working so far:
First prove that there is a q-ary code of length 5 and distance 3 with exactly $\frac{q^5}{5q-4}$ codewords. consider the spheres of radius 1 centred on codewords. Each such sphere contains 1 + 5 = 6 words. Since the code has distance 3, no two such spheres intersect. Otehrwise we would have a pair of codewords at distance 2 or less. Since there are $\frac{q^5}{5q-4}$ codewords, there are $\frac{6q^5}{5q-4}$ distinct words in these spheres. However there are only $q^5$ distince q-ary words of length 5. therefore we have to show that
$\frac{6q^5}{5q-4}$ = $q^5$ for some q that is a natural non-zero number.

i worked out q = 2 therefore such a code exists. but now im having problems proving that no q-ary code with MORE THAN $\frac{q^5}{5q-4}$ codewords exists. also, with q = 2 the no of codewords = $\frac{16}{3}$ can anyone tell me why this isnt a whole number?

2. There is some mistake in your argument.
If you look at a sphere with radius one, then in order a word has distance 1 to the center if they differ in one place. Since it is of length 5 then we can choose one of this place. BUT for each place we have a (q-1) way to change it . So the number of codes in this sphere is 1+5(q-1)=5q-4.
As you said all of this sphere are disjoint. If there are N codes then we need the total word to be less or equal to q^5. Then we need
$(5q-4)N\leq q^5$. There fore $N\leq \frac{q^5}{5q-4}$ as desired.

3. Originally Posted by watchmath
There is some mistake in your argument.
If you look at a sphere with radius one, then in order a word has distance 1 to the center if they differ in one place. Since it is of length 5 then we can choose one of this place. BUT for each place we have a (q-1) way to change it . So the number of codes in this sphere is 1+5(q-1)=5q-4.
As you said all of this sphere are disjoint. If there are N codes then we need the total word to be less or equal to q^5. Then we need
$(5q-4)N\leq q^5$. There fore $N\leq \frac{q^5}{5q-4}$ as desired.
thanks i sort of understand what ur saying, but how do i solve $N\leq \frac{q^5}{5q-4}$? or how do i prove that there is no such answer $N$ when i dont even know $q$?

4. Maybe my wording is not quite nice.

Another attempt.
Let N be the number of codewords. As I proved earlier in each ball there are 1+5(q-1)=5q-4 q-ary words. Since we have N balls (because the center is the codewords) and the union of all of these balls is a subset of the set of all q-ary (some q-ary words can be outside the balls) then N(5q-4) (the number of all q-ary words in the balls) can not be bigger than the number of all q-ary, that is $N(5q-4)\leq q^5$. From this we conclude that $N\leq \frac{q^5}{5q-4}$. Therefore N, the number of N words is not more than $\frac{q^5}{5q-4}$.

5. Thanks so much!! Proof by contradiction i love it