TOPICS
Search

McEliece-Rodemich-Rumsey-Welch Bound

The McEliece-Rodemich-Rumsey-Welch (MRRW) bound is an asymptotic upper bound for the rate R_2(delta) of a binary code of relative minimum distance delta. Define the binary entropy function and an auxiliary function by

H_2(x)=-xlog_2x-(1-x)log_2(1-x),
(1)

with 0log_20=0. For 0<=v<=1, define

g(v)=H_2((1-sqrt(1-v))/2).
(2)

The first MRRW exponent is

M_1(delta)=H_2(1/2-sqrt(delta(1-delta))),
(3)

and the optimized second MRRW exponent is

M_2(delta)=min_(0<=tau<=1-2delta){1+g(tau^2)-g(tau^2+2deltatau+2delta)}.
(4)

For 0<delta<1/2, the classical bound is R_2(delta)<=M_2(delta) (McEliece et al. 1977).

OpenAI (2026) enlarged the two classical variational families as follows. For 0<=b<a<=1/2, set

Gamma_H(a,b)=(2(a-b)(1-a-b))/(sqrt(a(1-a))),
(5)

and

kappa_H(delta)=inf_(0<=b<a<=1/2; Gamma_H(a,b)>1-2delta){H_2(a)-H_2(b)}.
(6)

For parameters

alpha in (delta/2,1/2),beta in [0,alpha/2),gamma in [0,(1-alpha)/2)
(7)
u in (beta+gamma,min{alpha,alpha-beta+gamma,1-alpha+beta-gamma}).
(8)

define

z=1-2u,
(9)
m=1-2alpha,
(10)
zeta=1-2beta-2gamma,
(11)
xi=1-2alpha+2beta-2gamma,
(12)
Lambda_(alpha,beta,gamma)(u)=((zetaxi-mz^2)^2)/(z^2(1-m^2)(1-z^2))+((z^2-xi^2)(zeta^2-z^2))/(z^2(1-m^2)sqrt(1-z^2)).
(13)

Let D_delta be the set of quadruples (alpha,beta,gamma,u) satisfying these ranges and

Lambda_(alpha,beta,gamma)(u)>1-delta/(2alpha(1-alpha)).
(14)

The constant-weight exponent is

kappa_(CW)(delta)=inf_((alpha,beta,gamma,u) in D_delta)[1-H_2(alpha)+H_2(u)-alphaH_2(beta/alpha)-(1-alpha)H_2(gamma/(1-alpha))].
(15)

Finally, the new binary-code exponent is

kappa_(bin)(delta)=min{kappa_H(delta),kappa_(CW)(delta)},
(16)

and OpenAI proved

R_2(delta)<=kappa_(bin)(delta)<M_2(delta) for 0<delta<1/2.
(17)

The comparison is strict for every fixed delta in this interval. The boundary choices b=0 and beta=gamma=0 recover the classical M_1 and constant-weight families. Positive harmonic degrees strictly improve every interior minimizing layer; when the endpoint tau=1-2delta minimizes M_2, so that M_2=M_1, the whole-cube family instead gives the strict improvement.

See also

Binary Code, Coding Theory, Hamming Distance

Explore with Wolfram|Alpha

References

McEliece, R. J.; Rodemich, E. R.; Rumsey, H. C. Jr.; and Welch, L. R. "New Upper Bounds on the Rate of a Code via the Delsarte-MacWilliams Inequalities." IEEE Trans. Inform. Th. 23, 157-166, 1977. https://doi.org/10.1109/TIT.1977.1055688.OpenAI. "Improved Bounds for Binary and Spherical Codes." Ch. 2 in Ten Advances in Mathematics and Theoretical Computer Science. San Francisco, CA: OpenAI, Aug. 1, 2026. https://cdn.openai.com/pdf/ten-proofs-oai.pdf.

Cite this as:

Weisstein, Eric W. "McEliece-Rodemich-Rumsey-Welch Bound." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/McEliece-Rodemich-Rumsey-WelchBound.html

Subject classifications