Determining if a code exists, given the parameters $(n, M, d)$

Question

I am looking at some questions which ask the same as above, with values for $n$, $M$ (or $k$ for linear codes), and $d$.

My notes define several bounds:

1. The Sphere-Packing Bound
2. The Singleton Bound
3. The Varshamov Bound (and the very similar Gilbert Bound)
4. The Plotkin Bound
5. The Griesmer Bound

However, the notes do not say anything about what it means if each of these bounds' inequalities are not satisfied. I understand that for some, if not all of them, if they are not satisfied, then we cannot say that the code does not exist.

So my main two questions are:

1. Am I correct in saying that if any one of these five bounds is satisfied for a set of given parameters, then we can conclude that the code does exist?

2. If a set of parameters do not satisfy any of the five bounds, then is it safe to say that a code does not exist?

I am lost with how to approach these types of questions, given that I have these five bounds. Do I just iteratively try each bound until one of them is satisfied?

Answer 1

You need to do a bit of serious research, this is a somewhat complicated topic. Some of these are existence some are nonexistence bounds.

Gilbert-Varshamov says there is a code with at least so many codewords given $k$ and $d$. Finding a code with these parameters is a hard problem. This is an existence bound.

The others are non-existence bounds, i.e., upper bounds on the largest possible number of codewords in a code with other parameters specified [or they can be recast that way]. The only thing you can say with certainty is that codes which are larger (in number of codewords) than these non-existance bounds do not exist.

In McWilliams and Sloane's book as well as in Stephen Roman's book, there are some figures which make this relationship clearer.

By the way, the wikipedia pages on these bounds are quite good. Also, google Atri Rudra's notes from SUNY Buffalo.

Search for bounds on codes using "images" as a choice on Google. Asymptotically one of the most interesting results is the relationship between Gilbert Varshamov lower bound and the "4 Americans" (McEliece, Rudemich, Rumsey, Welch) upper bound. So asymptotically, all codes must be between these two curves [figure reproduced below].