$x<y \implies A(n,x)>A(n,y)$?

Question

Let $A(n,d)$ denote the largest $M$ such that there exists a $(n,M,d)$ code. (Let's fix some alphabet, say binary)

For example:

$A(n,1) = 2^n$

$A(n,2) = 2^{n-1}$

$A(n,n) = 2$

Well, looking at this pattern, I thought that the sequence $A(n,d)$ is decreasing in $d$, i.e. if I have $0 < d_1 < d_2 < n$ then is it true that $A(n,d_1)>A(n,d_2)$?

Here's how I proceeded (but got stuck):

Let $M = A(n,d_1)$ and $C$ be a $(n,M,d_1)$ code. Assume that $0 \in C$ (otherwise we can "shift" the code).

I want to add another codeword $y$ to $C$ such that $d(0,y) = d_2$ and $d(x,y) \geq d_2$ $\forall x \in C$.

In other words, I want to find a $y$ of weight $d_2$ such that it is atleast $d_2$ apart from all other codes in $C$.

Having no information about structure of $C$, it seems like this might not be possible.

Can somebody help me proceed with this idea?

Or is there a "nice" counter-example to this?

Answer 1

Assuming binary codes are to be used, it is easy to come up with counter examples for high values of $d$.

Consider the case $n=5$, $d_1=4$, $d_2=5$. I claim that $A(5,4)=A(5,5)=2$.

• If $x,y,z$ are three vectors of five bits such that $d(x,y)\ge4$ and $d(x,z)\ge4$, then $x$ and $y$ agree on at most a single position. Similarly $x$ and $z$ agree on at most single position.
• Therefore $y$ and $z$ agree on at least three bit positions (=those they both disagree with $x$ on), and thus $d(y,z)\le2$.
• So it is impossible to find a code of size three with minimum distance $\ge4$.

---

You hopefully see how increasing the alphabet to larger than binary ruins the above argument.