So, the supposedly the sharpest one among all known bounds is somehow poorer than the bound you learn in Coding Theory 101 if the alphabet size $q$ approaches infinity. I think the reason you find it funny lies in what you mean by "large $q$."

You can think this way: *If the parameter $q$ is large compared to the code length $n$, the Singleton bound is an extremely sharp, invincible upper bound.* In fact, it's best possible in the sense that there are infinitely many nontrivial codes attaining it. I think that's why you got caught in a seemingly contradicting situation where the "best upper bound (MRRW)" fails to beat the "poor and elementary bound (Singleton)."

Here's a bit more formal explanation. The upper bounds on the information rate $R$ you're considering are asymptotic ones described by the *Hilbert entropy function*

$$H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x)$$

and the *relative distance* $\delta = \frac{d}{n}$, where $d$ is the minimum distance of a code. Bounds of this kind try to understand the behavior of the information rate when the code length $n$ tends to infinity for a fixed $\delta$.

More precisely, by writing the largest possible number of codewords for a $q$-ary code of length $n$ and relative distance $\delta$ as $A_q(n,\delta n)$, we would like to know the exact value of

$$R_q(\delta) = \lim_{n\rightarrow \infty}\sup n^{-1}\log_qA_q(n,\delta n).$$

The MRRW bound you mentioned is a pretty good upper bound on $R_q(\delta)$ obtained through linear programing. Of course, the plain, simple Singleton bound can also be viewed as an asymptotic upper bound if you simply rewrite it with $\delta$, i.e., you have $R \leq 1-\delta$.

Now, what you did to the MRRW bound seem to be simply applying

$$\lim_{q\rightarrow \infty}H_q(\delta) = \delta$$

to see what it's like when "$q$ is large." The problem is that, in order to get a meaningful upper bound better than the Singleton bound, you should consider exactly what you mean by "large $q$."

As you probably already know, there are codes that meet the Singleton bound. Indeed, it's the definition of *maximum separable distance (MDS)* codes. The famous *Reed-Solomon codes* are the canonical examples of this type of code, which are conjectured to have the "largest" $n$ relative to $q$ among all possible (linear) MDS codes. More generally, algebraic geometry codes can attain

$$R \geq 1 - \delta - \frac{1}{\sqrt{q}-1}$$

when prime power $q$ is a square. Hence, if your $q$ is in the range where MDS codes may exist, no general upper bound on $R$ can beat the Singleton bound unless it's a very contrived one. If $q$ is small enough compared to $n$ such that unbelievably strong codes like algebraic codes can be realized, you don't expect any other bound can beat it.

So, if you would like a stronger asymptotic upper bound than the Singleton bound, you have to at least rule out the existence of MDS codes by making $q$ grow slow enough. Here's one theorem I know that can be used for this purpose:

If there exists a $q$-ary MDS code of length $n$ and minimum distance $d$, then $q \geq n-d+2.$

(For the proof, see L. M. G. M. Tolhuizen, On maximum distance separable codes over alphabets of arbitrary size, *Proc. IEEE Int. Symp. Inf. Theory* (1994) 431.)

So, by fixing the relative distance $\delta$, the inequality can be rewritten as $q \geq n(1-\delta)+2$. By this necessary condition for the existence of an MDS code, if you only allow $q$ to be always smaller than the right-hand side when driving $n$ to infinity, your favorite general upper bound may have a chance to beat the Singleton bound.

MDS codes and other very powerful error-correcting codes are extremely important and have various interesting connections to other fields both inside and outside of mathematics. So if you ask a real coding theorist, I think they know the best theorem you can exploit to rule out the existence of MDS codes and also the best methods to get sharp upper bounds on $R$ for $q$ of your favorite size and growth rate.

notvote to close it here just over this, but still wanted to give the links for everybodies benefit. $\endgroup$ – user9072 Oct 30 '12 at 10:21