<p>This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.6304" rel="nofollow">the paper</a> "On the optimum of Delsarte's linear program" by Samorodnitsky (1998). </p>

<p>Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$.  Even for $q=2$, this is a complicated analysis, so I don't know whether anybody has performed it for larger $q$.</p>

CC BY-SA 3.0
2013-09-19T21:10:16.337Z
2013-09-19T21:10:16.337Z
Peter Shor 
<p>Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation approach) which states that the rate $R(\delta)$ corresponding to a relative distance of $\delta$ is such that:
\begin{equation*}R(\delta) \leq H_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation*}
where H is the (binary) entropy function.
(A slight improvement of the above exists in the binary case, but within the same framework)
In the case of q-ary codes, i.e. codes over $\mathbb F _q ^n$, the above bound is generalized to:
\begin{equation*}R(\delta) \leq H_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation*}
My question is as follows:
For larger alphabet size q, the above bound seems to weaken significantly. In fact, observing the growth of the above bound as $q \rightarrow \infty$, we see that:
\begin{equation*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}})  \end{equation*}
Thus, it seems to get worse than even the Singleton bound $R(\delta) \leq 1-\delta$.</p>

<p>So which is the best bound for large alphabet size $q$? Or am I wrong in the above conclusion that the MRRW bound is worse than even the Singleton bound for larger $q$?
Also, could someone direct me to references for comparisons of different upper bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.</p>

<co.combinatorics><it.information-theory><coding-theory><upper-bounds>
Best upper bound on rate for q-ary codes
Brazen
# Best upper bound on rate for q-ary codes

(Asked by: username_0 on 2012-10-30)

Among the many upper bounds for families of codes in $\mathbb F \_2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation approach) which states that the rate $R(\delta)$ corresponding to a relative distance of $\delta$ is such that:
\begin{equation\*}R(\delta) \leq H\_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation\*}
where H is the (binary) entropy function.
(A slight improvement of the above exists in the binary case, but within the same framework)
In the case of q-ary codes, i.e. codes over $\mathbb F \_q ^n$, the above bound is generalized to:
\begin{equation\*}R(\delta) \leq H\_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation\*}
My question is as follows:
For larger alphabet size q, the above bound seems to weaken significantly. In fact, observing the growth of the above bound as $q \rightarrow \infty$, we see that:
\begin{equation\*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}}) \end{equation\*}
Thus, it seems to get worse than even the Singleton bound $R(\delta) \leq 1-\delta$.

So which is the best bound for large alphabet size $q$? Or am I wrong in the above conclusion that the MRRW bound is worse than even the Singleton bound for larger $q$?
Also, could someone direct me to references for comparisons of different upper bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.

**Tags:** co.combinatorics, it.information-theory, coding-theory, upper-bounds


---

## 1 answers

### Answer by username_1 on 2013-09-19. Score: 3

This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see [the paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.6304) "On the optimum of Delsarte's linear program" by Samorodnitsky (1998).

Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$. Even for $q=2$, this is a complicated analysis, so I don't know whether anybody has performed it for larger $q$.


---

