1

An improvement of the asymptotic Elias bound for
non-binary codes.
Krishna Kaipa

arXiv:1705.07785v3 [] 27 Feb 2018

Abstract
For non-binary codes the Elias bound is a good upper bound for the asymptotic information rate at low relative
minimum distance, where as the Plotkin bound is better at high relative minimum distance. In this work, we obtain
a hybrid of these bounds which improves both. This in turn is based on the anticode bound which is a hybrid of
the Hamming and Singleton bounds and improves both bounds. The question of convexity of the asymptotic rate
function is an important open question. We conjecture a much weaker form of the convexity, and we show that
our bounds follow immediately if we assume the conjecture.
Index Terms
information rate, size of a code, anticode.

I. I NTRODUCTION
Let Aq (n, d; L) denote the maximum size of a code of length n, minimum distance at least d, and
contained in a subset L ⊂ F n , where F is an alphabet of finite size q. A central problem in coding theory
is to obtain good upper and lower bounds for Aq (n, d) = Aq (n, d; F n ). The asymptotic version of this
quantity is the asymptotic information rate function:
α(x) = lim sup n−1 logq Aq (n, xn), x ∈ [0, 1].

(1)

n→∞

The quantities Aq (n, d; L) and Aq (n, d) are related by the inequality
Aq (n, d) ≤ q n Aq (n, d; L)/|L|,

(2)

known as the Bassalygo-Elias lemma. Taking L to be a Hamming ball of diameter w, and choosing w
optimally gives, at the asymptotic level the Hamming and the Elias upper bounds.
αH (x) = 1 − Hq (x/2), x ∈ [0, 1].
p
αE (x) = αH (2θ(1 − 1 − x/θ)), x ∈ [0, θ].

(3)
(4)

The bound αE is better than αH for all x. Here Hq (x) is the entropy function (9), and θ := 1 − q −1 .
An anticode of diameter w in F n is any subset of F n with Hamming diameter w. Let A∗q (n, w) denote
the maximum size of an anticode of diameter at most w in F n . In contrast to the situation with Aq (n, d),
the quantity A∗q (n, d) was explicitly determined by Ahlswede and Khachatrian in [1]. From their result,
it is easy to determine the asymptotic quantity α∗ (x) = limn→∞ n−1 logq A∗q (n, xn). We actually do not
need the results of [1], however it is the main inspiration for this work. Taking L to be an A∗q (n, w)
anticode in (2), and choosing w optimally, we get the following two bounds which improve αH and αE
respectively.
Theorem 1. (hybrid Hamming-Singleton bound)
(
1 − Hq ( x2 )
if x ∈ [0, 2/q]
αHS (x) =
(1 − x)Hq (1) if x ∈ [2/q, 1].
K. Kaipa is with the Department of Mathematics at the Indian Institute of Science and Education Research, Pune 411008, India
(email: kaipa@iiserpune.ac.in). The author was supported by the Science and Engineering Research Board, Govt. of India, under Project
EMR/2016/005578.

2

The bound αHS improves the Hamming and the Singleton bounds. It is ∪-convex and continuously
differentiable.
Theorem 2. (hybrid Elias-Plotkin bound) Let q > 2.
(
√
2q−3
]
1 − Hq (θ − θ2 − xθ) if x ∈ [0, q(q−1)
αEP (x) =
(q−1)Hq (1)
2q−3
(θ − x) q−2
if x ∈ [ q(q−1) , θ]
The bound αEP improves the Elias and Plotkin bounds. It is ∪-convex and continuously differentiable.
It is not known if the function α(x) itself is ∪-convex, although it is tempting to believe that it is. We
propose a weaker conjecture:
Conjecture 1. The function

α(x)
θ−x

is decreasing. In other words

α(tx + (1 − t)θ) ≤ tα(x) + (1 − t)α(θ), t ∈ [0, 1].
As evidence for this conjecture, we will show that theorems 1 and 2 follow very easily if we admit the
truth of the conjecture.
The bound αEP in Theorem 2 is an elementary and explicit correction to the classical Elias bound.
It does not however improve the upper-bounds obtained by the linear programming approach, like the
second MRRW bound αM RRW 2 (due to Aaltonen [2]) or the further improvement of αM RRW 2 due to
Ben-Haim and Litsyn [3, Theorem 7]. The reasons for this are as follows: For small δ we have αEP (δ) =
αE (δ) ≥ αM RRW 2 (δ). For large δ, the inequality αEP (δ) > αM RRW 2 (δ) follows from the fact that αEP (δ)
has a non-zero slope at δ = 1 − 1/q where as the actual function α(δ) and the bound αM RRW 2 have zero
slope at δ = 1 − 1/q.
The paper is organized as follows. In section II, we collect some results on size of anticodes, which we
use in section III to prove Theorems 1 and 2. We discuss Conjecture 1 in section IV.
II. S IZE OF ANTICODES
We recall that A∗q (n, d) is the maximum size of an anticode of diameter at most d in F n . If we take L
to be an anticode of size A∗q (n, d − 1) then clearly Aq (n, d; L) = 1. Using this in (2), we get a bound
Aq (n, d) ≤ q n /A∗q (n, d − 1),

(5)

known as Delsarte’s code-anticode bound [4]. Taking d = xn where x ∈ [0, 1] we get
n−1 logq Aq (n, xn) ≤ 1 − n−1 logq A∗q (n, xn − 1).
Taking lim supn→∞ we get:

α(x) ≤ 1 − α∗ (x),

(6)

α∗ (x) = lim inf n−1 logq A∗q (n, xn).

(7)

where
n→∞

This is the the asymptotic form of (5). We use the notation B(r; n) and Vq (n, r) to denote a Hamming
ball of radius r in F n and its volume respectively. The ball B(t; n) where t = b(d − 1)/2c in F n is an
anticode of diameter at most d − 1. Let F n = F d−1 × F n−d+1 and let v ∈ F n−d+1 be a fixed word. Sets
of the form F d−1 × {v} of size q d−1 are also anticodes of diameter d − 1. It follows that:
α∗ (x) ≥ max{Hq (x/2), x}.
Here, we have used the well known formula:
lim n−1 logq Vq (n, tn) = Hq (t), t ∈ [0, θ],

n→∞

(8)

3

where,
1
) + (1 − x) logq ( 1−x
), x ∈ [0, 1].
Hq (x) = x logq ( q−1
x

(9)

While the convexity of α(x) is an open question, it is quite easy to see that:
Lemma 1. The function α∗ (x) is ∩-convex.
F

n1

Proof: If S1 ⊂ F n1 and S2 ⊂ F n2 are anticodes of diameters d1 and d2 respectively, then S1 × S2 ⊂
× F n2 is an anticode of diameter d1 + d2 . Taking Si to be A∗q (ni , di ) anticodes, we immediately get
A∗q (n1 + n2 , d1 + d2 ) ≥ A∗q (n1 , d1 )A∗q (n2 , d2 ).

Let n = n1 + n2 go to infinity with n1 /n = t + o(1), d1 /n1 = x + o(1) and d2 /n2 = y + o(1). Applying
lim inf n→∞ n−1 logq to this inequality we get:
α∗ (tx + (1 − t)y) ≥ tα∗ (x) + (1 − t)α∗ (y), t ∈ [0, 1].
We note that with codes we have d(C1 ×C2 ) = min{d(C1 ), d(C2 )}, which is why the above proof method
does not apply to the question of convexity of α(x). From (8) and Lemma 1 we get:
α∗ (tx + (1 − t)y) ≥ tHq (x/2) + (1 − t)y, t ∈ [0, 1].
Let δ = tx + (1 − t)y. We can rewrite this as
α∗ (δ) ≥ f (x, y),
where f : [0, δ) × (δ, 1] is defined by
f (x, y) =

y−δ
(Hq (x/2)
y−x

− x) + δ.

(10)

We note that
(y−x)2 ∂f
(x, y)
δ−x ∂y
x(y−x)2

∂f
(x, y)
y(y−δ) ∂x

= Hq (x/2) − x,

= Hq ( x2 ) − x + (1 − xy ) logq (1 − x2 ).

There is a unique positive number b > 0 satisfying Hq (b/2) = b (where the Hamming and Singleton
bounds intersect). Therefore, Hq (x/2) − x has the same sign as b − x. Using this in (10), we see that
f (x, y) ≤ δ for x ≥ b. Therefore, in order to maximize f (x, y) it suffices to consider x < b. We note that
∂f
(x, y) has the same sign as H(x/2) − x and hence that of b − x. Since x < b, we see that for fixed
∂y
x < b, the function f (x, y) is maximized for y = 1. We are now reduced to maximizing
q (x/2)
f (x, 1) = 1 − (1 − δ) 1−H1−x
, x ∈ [0, δ].

Lemma 2. Let g(x) =

1−Hq (x/2)
1−x

for x ∈ [0, 1].
sign(g 0 (x)) = sign(x − 2q ).

Proof: We calculate:
g 0 (x) =

1
2(1−x)2

2

x(2−x)
logq ( q 4(q−1)
).

2

x(2−x)
Therefore sign(g 0 (x)) = sign( q 4(q−1)
− 1). Next, we note that
q 2 x(2−x)
4(q−1)

− 1 = q(x − 2q ) (q−2)+q(1−x)
4(q−1)

has the same sign as x − 2/q, as was to be shown. A stronger assertion is that g(x) is in fact ∪-convex:
differentiating once more, we get:
2

/4
1
1
ln(q)(1 − x)3 g 00 (x) = ln( qq−1
) + ( 2x−x
2 − 1 − ln( 2x−x2 ))

4

We note that q 2 ≥ 4(q − 1), and hence the first term is non-negative. The remaining parenthetical term is
non-negative using the inequality
t − 1 − ln(t) ≥ 0 for t ≥ 1,
(11)
and the fact that t = 1/(2x − x2 ) ≥ 1 for x ∈ (0, 1].
It follows from Lemma 2 that
q (x/2)
argminx∈[0,δ] 1−H1−x
= min{δ, 2/q}.

(12)

(
Hq (x/2)
if x ∈ [0, 2/q]
β(x) =
1 − (1 − x)Hq (1) if x ∈ [2/q, 1].

(13)

Therefore we obtain the bound:
Theorem 3. α∗ (x) ≥ β(x) where

Moreover, β(x) is continuously differentiable and ∩-convex.
We have used the relation

1−Hq (1/q)
1−2/q

= Hq (1) = logq (q − 1).

(14)

The function β(x) is continuously differentiable because the component for x ≥ 2/q is just the tangent
line at x = 2/q to the component for x ≤ 2/q, i.e. to Hq (x/2). We note that β 0 (x) equals Hq0 (x/2)/2 for
x ≤ 2/q and Hq0 (1/q)/2 for x ≥ 2/q. Since β 0 (x) is non-increasing, it follows that β(x) is ∩-convex.
In the next lemma, we show that there is a sequence of anticodes Sn ⊂ F n of diameter at most δn
such that limn→∞ n−1 logq |Sn | equals β(δ), i.e. the lower bound on α∗ (δ) given in theorem 3.
Lemma 3. Consider the anticodes S(d, n) of diameter d in F n (taken from [1]) given by
S(d, n) = B(rd,n ; n − d + 2rd,n ) × F d−2rd,n , where
rd,n = max{0, min{d d−1
e, d n−d−q+1
e}}.
2
q−2
Then limn→∞ n−1 logq |S(δn, n)| = β(δ).
Proof: We note that

(
rδn,n
n→∞ n

ρ = lim

=

δ
2
1−δ
q−2

if δ ∈ [0, 2/q]
if δ ∈ [2/q, 1].

Also limn→∞ n−1 logq |S(δn, n)| equals
ρ
(1 − δ + 2ρ)Hq ( 1−δ+2ρ
) + (δ − 2ρ),

which simplifies to Hq (δ/2) if δ ≤ 2/q and (on using (14)) to 1 − (1 − δ)Hq (1) if δ ≥ 2/q. This is the
same as β(δ).
We now have all the results we need for proving theorems 1 and 2. However, we will state a remarkable
theorem due to Ahlswede and Khachatrian [1], which we will not need. We also obtain an asymptotic
version of their result and record it as a corollary, as it does not seem to have appeared in literature. In brief
their theorem states that A∗q (n, d) equals |S(d, n)|. Moreover any A∗q (n, d) anticode is Hamming isometric
to the anticode S(d, n) (with some exceptions). At the asymptotic level, the result is again remarkable:
The lower bound β(δ) for α∗ (δ) given in theorem 3 is actually the exact value of α∗ (δ). Moreover α∗ (δ)
need not have been defined using lim inf n→∞ as limn→∞ n−1 logq A∗q (n, δn) already exists.
Theorem. [1] Given q ≥ 2 and integers 0 ≤ d ≤ n, let rd,n and S(d, n) be as in Lemma 3. Then,
A∗q (n, d) = |S(d, n)|.

5

Moreover, up to a Hamming isometry of F n an anticode S of size A∗q (n, d) must be:
• S(d, n)
• or S(d, n) with rd,n replaced with rd,n − 1. This case is possible only if (n − d − 1)/(q − 2) is a
positive integer not exceeding d/2.
Corollary 1.

(
Hq (x/2)
α∗ (x) =
1 − (1 − x)Hq (1)

if 0 ≤ x ≤ 2/q
if 2/q ≤ x ≤ 1.

Proof: It follows from the theorem of Ahlswede and Khachatrian, together with Lemma 3 that
logq A∗q (n,δn)
n
n→∞

lim

Therefore
α∗ (δ) = lim inf
n→∞

= lim

n→∞

logq A∗q (n,δn)
n

logq |S(δn,n)|
n

= βq (δ).

logq A∗q (n,δn)
n
n→∞

= lim

= β(δ).

III. P ROOFS OF THEOREMS 1 AND 2
A. Proof of Theorem 1
If we use the bound α∗ (x) ≥ β(x) of Theorem 3 in the inequality α(x) ≤ 1 − α∗ (x) (see (6)), we
obtain the bound
α(x) ≤ 1 − β(x) =: αHS (x).
Since β(x) is ∩-convex and continuously differentiable (see Theorem 3), it follows that αHS (x) is ∪convex and continuously-differentiable. To show that αHS (x) ≤ αS (x) = 1 − x, we note that αS (x) being
the secant line to αHS (x) between (0, αHS (0)) and (1, αHS (1)), lies above the graph of αHS (x) as the
latter is ∪-convex. To prove that αHS (x) improves αH (x) we note that αHS (x) coincides with αH (x) for
x ≤ 2/q, and for x ≥ 2/q, Lemma 2 implies that αH (x) ≥ (1 − x)Hq (1) = αHS (x). This finishes the
proof of Theorem 1.
It is worth noting that (12) implies the following formula for αHS (δ):
αH (x)(1−δ)
.
1−x
x∈[0,δ]

αHS (δ) = min
Since

θ−δ
θ−x

≤

1−δ
1−x

(15)

for x ∈ [0, δ] and δ ≤ θ, we get
αHS (δ) ≥ αHP (δ) := min

x∈[0,δ]

αH (x)(θ−δ)
.
θ−x

(16)

It can be shown (see subsection III-C) that αHP (δ) is an upper bound for α(δ) which improves both the
Hamming and Plotkin bounds.
B. Proof of Theorem 2
It will be convenient to identify the alphabet F with the abelian group Z/qZ. Given 0 ≤ δ ≤ ω, let
wn = bωnc and dn = bδnc. We take Ln ⊂ F n to be the anticode (from Lemma 3):
Ln = B(rn ; n − wn + 2rn ) × F wn −2rn , where
n −q+1
e}}.
rn = max{0, min{d wn2−1 e, d n−wq−2

(17)

6

We will take the balls B(r; m) to be centered at (0, . . . , 0) ∈ F m . As in Lemma 3, we have
(
ω
if ω ∈ [0, 2/q]
2
ρ := lim rnn = 1−ω
n→∞
if ω ∈ [2/q, 1].
q−2

(18)

We also note that Lemma 3 gives
lim n−1 logq |Ln | = β(ω) = 1 − αHS (ω).

(19)

n→∞

Let Aq (n, dn ; Ln ) be the maximum possible size of a code contained in Ln and having minimum distance
at least dn .
Theorem 4. limn→∞ n−1 logq Aq (n, dn ; Ln ) = 0 if
ρ
θ(1−ω+2ρ)

≤1−

q

1−δ/θ
.
1−ω+2ρ

(20)

Proof: Our proof is similar to the standard proof of the analogous result for the Elias bound (which
corresponds to taking ρ = ω/2 instead of the prescription (18)). First let C ⊂ L be a code of size
M = Aq (n, d; L), where L ⊂ F n is the anticode L = B(r; n − w + 2r) × F w−2r for some r ≤ w/2. Let
γ1 (C) = (M n)

−1

n X
X

m(i, a)2 ,

i=1 a∈F

P
where m(i, a) = #{c ∈ C : ci = a}. We note that M = a∈F m(i, a), and that
XX
γ1
).
M (M − 1)d ≤
d(c, c0 ) = nM 2 (1 − M
c∈C c0 ∈C

We can rewrite this as:
M≤

γ1
M

d/n
, provided
− (1 − nd )

γ1
M

> 1 − nd .

For n − w + 2r < i ≤ n we use Cauchy-Schwarz inequality to get
n
X

1
M 2 (w−2r)

X

P

a∈F

(21)
m(i, a)2 ≥ M 2 /q. In particular

m(i, a)2 ≥ 1q .

(22)

i=n−w+2r+1 a∈F

Let π1 be the projection of F n = F n−w+2r × F w−2r on to the factor F n−w+2r . We note that for c ∈ C,
we have wt(π1 (c)) < r because π1 (C) ⊂ B(r; n − w + 2r). Here wt(v) is the number of nonzero entries
of v. Therefore
n−w+2r
X X
m(i, a) ≤ M r.
i=1

Since

Pn−w+2r P
i=1

a

a6=0

m(i, a) = M (n − w + 2r) we get:
S=

n−w+2r
X

m(i, 0) ≥ (n − w + r)M.

i=1

In particular
S
M (n−w+2r)

We note that

P

a6=0

−

1
q

≥

n−w+r
n−w+2r

−

1
q

=θ−

r
.
n−w+2r

m(i, a) = M − m(i, 0). By Cauchy-Schwarz inequality:
n−w+2r
X
i=1

m(i, 0)2 ≥ S 2 /(n − w + 2r), and

(23)

7

X

m(i, a)2 ≥ (M − m(i, 0))2 /(q − 1)

a6=0

Since

Pn−w+2r P
i=1

a∈F

m(i, a)2 equals
!

n−w+2r
X

m(i, 0)2 +

i=1

X

m(i, a)2 ,

a6=0

we get:
n−w+2r
X X
i=1

n−w+2r
X 

2

m(i, a) ≥

qm(i,0)2 +M 2 −2M m(i,0)
q−1



i=1

a∈F

This can be rewritten as:
1
M 2 (n−w+2r)

n−w+2r
X X
i=1

S
m(i, a)2 ≥ 1θ ( M (n−w+2r)
− 1q )2 +

1
q

a∈F

Combining this with (22) we get:
γ1
M

≥

n−w+2r
S
( M (n−w+2r)
nθ

γ1
M

−

− q −1 )2 + 1q .

Using (23) this can be written as:
1
q

≥

n−w+2r
nθ

r
)2 .
n−w+2r

(θ −

Now let Cn ⊂ Ln be a sequence of codes of size Mn = Aq (n, dn ; Ln ). The preceding inequality gives:
γ1 (Cn )
Mn

−

1
q

≥

1−ω+2ρ
θ

(θ −

ρ
)2
1−ω+2ρ

+ o(1).

Using this in (21), we get:
Mn ≤

1−ω+2ρ
θ

δ + o(1)
,
ρ
(θ − 1−ω+2ρ
)2 − (θ − δ) + o(1)

provided the denominator is a positive number. Therefore, limn→∞ n−1 logq Mn = 0 provided
1−ω+2ρ
θ

(θ −

ρ
)2
1−ω+2ρ

This condition is the same as
ρ
θ(1−ω+2ρ)

≤1−

q

≥ θ − δ.
1−δ/θ
1−ω+2ρ

Since Mn = Aq (n, dn ; Ln ) this finishes the proof.
Using (2) we get:
logq Aq (n,dn )
log |L |
≤ 1 − qn n +
n

logq Aq (n,dn ;Ln )
.
n

Taking lim sup as n → ∞ and using the result of Theorem 4 and (19) we get:
α(δ) ≤ αHS (ωmax (δ)),

(24)

where ωmax (δ) is the largest value of ω for which the inequality (20) holds. In order to determine ωmax (δ),
we introduce functions f1 , f2 on [0, θ] defined by:
p
f1 (δ) = 2θ(1 − 1 − δ/θ)
(25)
2

f2 (δ)= 1 − (1 − δ/θ) (q−1)
q(q−2)
Lemma 4. Let q > 2.
1) f1 (δ) ≥ f2 (δ) with equality only at δ =

2q−3
.
q(q−1)

(26)

8

2q−3
.
2) f2 (δ) is the tangent line to f1 (δ) at δ = q(q−1)
2q−3
3) sign(f1 (δ) − 2/q) = sign(f2 (δ) − 2/q) = sign(δ − q(q−1)
).
p
Proof: Let f3 (δ) := 1 − q−1
1 − δ/θ. We observe that
q−2

sign(f3 (δ)) = sign(δ −

2q−3
).
q(q−1)

The three assertions to be proved follow respectively from the following three relations:

f1 (δ)−2/q
2(1−2/q)

=

f1 (δ) − f2 (δ) = (1 − 2/q) f3 (δ)2 ,
p
f10 (δ) − f20 (δ) = f3 (δ)/ 1 − δ/θ,
f2 (δ)−2/q
√
= f3 (δ).

(1−2/q)+θ

1−δ/θ

Proposition 1.
ωmax (δ) =

(
p
2θ(1 − 1 − δ/θ)
2

1 − (1 − δ/θ) (q−1)
q(q−2)

2q−3
if δ ∈ [0, q(q−1)
]
2q−3
if δ ∈ [ q(q−1)
, 1].

The function ωmax (δ) is increasing, continuously differentiable, and ∪-convex on [0, θ].
Proof: The inequality (20) reduces to
(
f1 (δ)
ω≤
f2 (δ)

if ρ = ω/2
if ρ = (1 − ω)/(2 − q),

where ρ is as given in (18). Therefore, for a given δ ∈ [0, θ], the quantity ωmax (δ) is the maximum element
of the set
{ω : δ ≤ ω ≤ min{f1 (δ), 2/q}} ∪ {ω : max{δ, 2/q} ≤ ω ≤ f2 (δ)}.
2q−3
2q−3
If δ ≥ q(q−1)
, then f2 (δ) ≥ 2/q (by Lemma 4) and hence, the maximum of this set is f2 (δ). If δ ≤ q(q−1)
,
then f2 (δ) ≤ f1 (δ) ≤ 2/q (by Lemma 4) and hence, the maximum of this set is f1 (δ). This proves the
asserted formula for ωmax (δ).
2q−3
We note that the second component of ωmax (δ) is the tangent line to the first component at x = q(q−1)
.
p
2q−3
Therefore ωmax (δ) is continuously differentiable. The derivative of ωmax (x) is 1/ 1 − x/θ for x ≤ q(q−1) ,
2q−3
and constant at q−1
for x ≥ q(q−1)
. Since the derivative is positive, the function is increasing. Since the
q−2
derivative is non-decreasing, we see that the function is ∪-convex.
Proof of αEP being an upper bound: We note from lemma 4 that

sign(ωmax (δ) − 2/q) = sign(δ −

2q−3
).
q(q−1)

Therefore αHS (ωmax (δ)) is just the function αEP (δ) defined in of theorem 2. The bound α(x) ≤ αEP (x)
now follows from (24).
Proof of αEP being continuously differentiable: The function αEP (x) = αHS (ωmax (x)) being a composition of continuously differentiable functions, is itself continuously differentiable.
Proof of αEP being ∪-convex: Both the functions αHS and ωmax are ∪-convex, but αHS is decreasing
and hence it is not obvious that αEP (x) = αHS (ωmax (x)) is ∪-convex. We will show instead that the
2q−3
0
0
00
derivative αEP
is non-decreasing. Since αEP
is constant for x ≥ q(q−1)
, it suffices to show that αE
(x) > 0
2q−3
for x ∈ (0, q(q−1) ]. This follows from the next lemma.

9

Lemma 5. The Elias bound αE (x) is ∪-convex on [0, δE ] and ∩-convex on [δE , θ] where δE satisfies:
2q−3
q(q−1)

Proof: Let Z(x) = θ(1 −

< δE < 43 ( q−4/3
).
q−1

p
1 − x/θ). A calculation shows that
4θ ln(q)(1 −

Z(x) 3 00
) αE (x)
θ

Z
ϕ(z) =

θ
z
1−θ
1−z

= ϕ(Z(x)), where

(1 − 1/t)dt.

To see this, we note: αE (x) = Hq (Z(x)) and hence
00
(x) =
ln(q)αE

Z0
Z(1−Z)

+ Z 00 ln( (q−1)(1−Z)
).
Z

Since Z 0 = 1/(2(1 − Z/θ)) and Z 00 = Z 0 /(2θ(1 − Z/θ)2 ), we get
Z θ
Z(x)
Z(x) 3 00
(1 − 1/t)dt,
4θ ln(q)(1 − θ ) αE (x) =
1−θ
1−Z(x)

00
as desired. It follows that sign(αE
(x)) = sign(ϕ(Z(x)). Next we note that Z(x) is increasing on [0, θ]
and
2q−3
) = 1/q, Z( 43 ( q−4/3
)) = 1/2.
Z( q(q−1)
q−1

It now suffices to show that
sign(ϕ(z)) = sign(zE − z), for some zE ∈ ( 1q , 12 ).
We note that
ϕ0 (z) = (z − 21 ) z2(θ−z)
2 (1−z)2 .
Thus ϕ(z) is decreasing on [0, 1/2] and increasing on [1/2, θ]. In order to show sign(ϕ(z)) = sign(zE − z)
for some zE ∈ (1/q, 1/2), it suffices to show that ϕ(1/q) > 0 and ϕ(1/2) < 0. We calculate
1
ϕ(1/q)
2

2q−3
= ( q−1
− 1 − ln( q−1
)) + ( 2q−2
− ln(2)).
2
2

Since q ≥ 3, we have q−1
≥ 1. The inequality (11) implies that the first parenthetical term above is
2
non-negative. Again q ≥ 3 implies
2q−3
2q−2

− ln(2) ≥

3
4

− ln(2) > 0,

and hence the second parenthetical term is positive. Thus ϕ(1/q) > 0.
Next, we note that ϕ(1/2) = 2 − 4/q − ln(q − 1). The function a(t) = 2 − 4/t − ln(t − 1) satisfies
2

a0 (t) = − t(t−2)
2 (t−1) ,
and a(3) = 2/3 − ln(2) < 0. Therefore a(t) < 0 for t ≥ 3, and hence ϕ(1/2) < 0 for all q ≥ 3.
Proof that αEP improves the Plotkin bound: We have already shown that αEP (x) is ∪-convex, and
hence αEP (x) lies below the secant line between x = 0 and x = θ, which is the Plotkin bound.
Proof that αEP improves the Elias bound: This does not readily follow from our results thus far, and
requires more work. The characterization of αEP (x) given in the next theorem clearly implies αEP (x) ≤
αE (x).
αE (x)(θ−δ)
.
θ−x
x∈[0,δ]

Theorem 5. αEP (δ) = min

10

1

0.8

0.6

αE (δ)
αEP (δ)

0.4

0.2

0

0

0.2

0.4

0.6

0.8

δ

Fig. 1. αE (δ) and αEP (δ) for q = 16.

2q−3
E (x)
is decreasing on [0, q(q−1)
] and
Proof: The theorem immediately follows if we show that αθ−x
2q−3
increasing on [ q(q−1) , θ]. We will use the notation from the proof of Lemma 5. Since αE (x) is ∩-convex
for x ≥ δE , it follows that the slope αE (x)/(θ − x) of the secant between x and θ is increasing. It remains
2q−3
2q−3
E (x)
is decreasing on [0, q(q−1)
] and increasing on [ q(q−1)
, δE ]. Since Z(x) is an increasing
to show that αθ−x
2q−3
2
function, with Z(0) = 0, Z( q(q−1) ) = 1/q, and (1 − x/θ) = (1 − z/θ) , it suffices to show that

h(z) =

1−Hq (z)
,
(θ−z)2

is decreasing on [0, 1/q] and increasing on [1/q, zE ] where zE = Z(δE ). A calculation shows that
Z z
3 0
ln(q)(θ − z) h (z) =
ϕ(t)dt.
1/q
z
To see this we note that either side of this equation evaluates to (θ + z) ln( (1−z)(q−1)
) + 2 ln(q(1 − z)).
Since ϕ(t) > 0 for t ∈ (0, zE ), we see

sign(h0 (z)) = sign(z − 1/q), z ∈ [0, zE ].
Thus we have also shown that h(z) is decreasing for z ∈ [0, 1/q] and increasing on [1/q, zE ] as required.
The bounds αHS , αHP and αEP are related as
αEP (δ) ≤ αHP (δ) ≤ αHS (δ).
We have already shown αHP (δ) ≤ αHS (δ) in (16). Since αE (x) ≤ αH (x) for all x, we note that
min
x∈[0,δ]

αE (x)(θ−δ)
θ−x

≤ min
x∈[0,δ]

αH (x)(θ−δ)
.
θ−x

Thus αEP (δ) ≤ αHP (δ). We end this section with a plot comparing αE (x) and αEP (x) for q = 16.
C. Another proof of Theorem 1
Another proof of αHS (x) being an upper bound for α(x) can be given using the following theorem of
Laihonen and Litsyn:
Theorem. [5] Let δ1 , δ2 , µ ∈ [0, 1].
α((1 − µ)δ1 + µδ2 ) ≤ (1 − µ)αH (δ1 ) + µα(δ2 ).

(27)

11

Proof: We give a quick proof. The result follows from the inequality:
q n1 Aq (n2 , d2 )
,
Aq (n1 + n2 , d1 + d2 ) ≤
Vq (n1 , d1 /2)
by taking n1 + n2 = n → ∞, and n1 /n, n2 /n, d1 /n1 and d2 /n2 going to 1 − µ, µ, δ1 and δ2 respectively.
The above inequality in turn comes from the Bassalygo-Elias lemma (2)
q n1 +n2 Aq (n1 + n2 , d1 + d2 ; L)
Aq (n1 + n2 , d1 + d2 ) ≤
,
|L|
by taking L = B(d1 /2; n1 ) × F n2 , and observing that Aq (n1 + n2 , d1 + d2 ; L) ≤ Aq (n2 , d2 ). (If C is a
Aq (n1 + n2 , d1 + d2 ; L) code, and π2 : F n1 × F n2 → F n2 is the projection on the second factor, then the
restriction of π2 to C is injective, and π2 (C) has minimum distance at least d2 .)
If we set δ2 = 1, δ1 = x and µ = (δ − δ1 )/(1 − δ1 ) in (27), we get:
α(y)
αH (x)
≤
for x ≤ y.
1−y
1−x
Thus,
= αHS (δ),
α(δ) ≤ min αH (x)(1−δ)
1−x
x∈[0,δ]

where we have used (15).
We now prove that the function αHP (δ) defined in (16) is an upper bound for α(δ). Taking δ2 = θ,
δ1 = x, and µ = (y − δ1 )/(θ − δ1 ) in (27), we get:
α(y)
αH (x)
≤
for x ≤ y
θ−y
θ−x
Thus
α(δ) ≤ min αH (x)(θ−δ)
= αHP (δ).
(28)
θ−x
x∈[0,δ]

It is not known if the inequality (27) (the theorem of Laihonen-Litsyn) holds if we replace αH by αE .
If such a result were true, then the derivation of the bound αHP (x) above with αH replaced with αE
would immediately yield Theorem 5. We believe that such an inequality
α((1 − µ)δ1 + µδ2 ) ≤ (1 − µ)αE (δ1 ) + µα(δ2 ),

(29)

must be true (it would surely be true if α(x) is ∪-convex), but we believe it cannot be obtained just by a
simple application of the Bassalygo-Elias lemma (2). If (29) holds, we can obtain an upper bound which
improves the Laihonen-Litsyn bound [5]. We recall that the Laihonen-Litsyn bound, which we denote
αHM RRW is a hybrid of the Hamming and MRRW bounds. It coincides with the Hamming bound for
δ ∈ [0, a] and with the MRRW bound for [b, θ] where a < b are points such that the straight line joining
(a, αH (a)) and (b, αM RRW (b)) is a common tangent to both αH at a and αM RRW at b. Since the Hamming
bound is good for small δ and the MRRW bound good for large δ, the Laihonen-Litsyn bound combines
the best features of both bounds in to a single bound. To obtain this bound, we note that (27) implies the
inequality
α((1 − µ)δ1 + µδ2 ) ≤ (1 − µ)αH (δ1 ) + µαM RRW (δ2 ).
We fix δ = (1 − µ)δ1 + µδ2 and choose δ1 and δ2 optimally in order to minimize the right hand side. This
yields the αHM RRW bound. Since the second MRRW bound αM RRW 2 improves the first MRRW bound
αM RRW , a better version αHM RRW 2 of the Laihonen-Litsyn bound (see [3, Theorem 2]) can be obtained
by using αM RRW 2 in place of αM RRW 2 . Since the Elias bound αE (δ) is better than the Hamming bound
αH (δ) for all δ, in case (29) is true, repeating this procedure with αE replacing αH , would yield the
hybrid Elias-MRRW bounds αEM RRW (δ), αEM RRW 2 (δ) which would improve the respective LaihonenLitsyn bounds αHM RRW , αHM RRW 2 (δ). We leave the question of the truth of (29) open.

12

IV. O N THE CONVEXITY OF α(x)
A fundamental open question about the function α(x) is whether it is ∪-convex. In other words is it
true that
α((1 − t)x + ty) ≤ (1 − t)α(x) + tα(y), t ∈ [0, 1].
(30)
It is worth noting that non-convex upper bounds like the Elias bound and the MRRW bound admit
corrections to the non-convex part: the bound αEP (x) for the Elias bound and the Aaltonen straight-line
bound (see the theorem below and the Appendix) for the MRRW bound. This may be viewed as some
kind of evidence supporting the truth of (30). It is known that (30) holds for x = 0 (for example by taking
δ1 = 0 in (27)). Another way to state this is that
(1 − α(x))/x is decreasing on [0, 1].
As a consequence, if αu (x) is any upper bound for α(x) we obtain a better upper bound
(1 − αu (x))δ
x∈[δ,θ]
x

α(δ) ≤ α̃u (δ) = 1 − max

(31)

To see this we use:
1−α(δ)
δ

≥

1−α(x)
x

≥

1−αu (x)
, for
x

x ∈ [δ, θ].

Thus 1−α(δ)
≥ maxx∈[δ,θ] (1−αxu (x)) as desired. If (1 − αu (x))/x is a decreasing function then the improved
δ
bound α̃u (x) coincides with αu (x), but otherwise α̃u (x) improves αu (x). For example let αu (x) be the
first MRRW bound αM RRW (x) =
p
p
Hq (( θ(1 − x) − x(1 − θ))2 ), x ∈ [0, θ].
It can be shown that that (1 − αM RRW (x))/x fails to be decreasing near x = 0, and similarly αM RRW (x)
fails to be ∪-convex near x = 0. This is immediately rectified by passing to the improved bound
α̃M RRW (x), resulting in the following theorem of Aaltonen.
Theorem. (Aaltonen bound) [6] [7, p.53] Let q > 2. α(x) ≤ α̃M RRW (x) where
(
q (1)
1 − xH
if x ∈ [0, (1 − 2q )2 ]
1−2/q
α̃M RRW (x) =
αM RRW (x) if x ∈ [(1 − 2q )2 , θ]

(32)

This bound is ∪-convex, continuously differentiable, and improves the MRRW bound.
We note that for x ≤ (1 − 2/q)2 the bound α̃M RRW (x) coincides with the tangent line to αM RRW (x) at
(1−2/q)2 . In particular α̃M RRW (x) is continuously differentiable. The assertion that α̃M RRW (x) improves
αM RRW (x) follows from the fact that α̃u (x) ≤ αu (x) for any upper bound αu (x) for α(x). The other
assertions are proved in the appendix.
On the other hand, it is not known if the convexity condition (30) holds for y = θ, in other words if
α(x)/(θ − x) is a decreasing function of x. We conjecture that this is true (see Conjecture 1). As evidence
for this conjecture, we now show that the bounds αEP , αHP and αHS can be obtained without doing any
work, if we assume the truth of Conjecture 1: if αu (x) is any upper bound for α(x) we obtain a better
upper bound
αu (x)(θ − δ)
α(δ) ≤ αu† (δ) := min
(33)
x∈[0,δ]
θ−x
To see this we use:
α(δ)
θ−δ

≤

α(x)
θ−x

≤

αu (x)
θ−x

for x ∈ [0, δ].

u (x)
Thus α(δ) ≤ minx∈[0,δ] αu (x)(θ−δ)
as desired. In case αθ−x
is a decreasing function then the improved
θ−x
†
†
bound αu (x) coincides with αu (x), but otherwise αu (x) improves αu (x). Taking αu (x) to be the Elias

13

bound, we get αu† (x) to be the bound αEP . This is the content of Theorem 5. Taking αu (x) to be the
Hamming bound, we get αu† (x) to be the bound αHP . This is the content of (28). Moreover, if α(x)/(θ−x)
is decreasing then α(x)/(1 − x) being the product of the non-negative decreasing functions α(x)/(θ − x)
. Taking αu (x) to be
and (θ − x)/(1 − x) is itself decreasing. Thus we obtain α(δ) ≤ minx∈[0,δ] αu (x)(1−δ)
1−x
αu (x)(1−δ)
is αHS (δ). This is the content of (15).
the Hamming bound, the bound minx∈[0,δ] 1−x
A PPENDIX A
A ALTONEN ’ S STRAIGHT- LINE BOUND
The bound α̃M RRW presented above was obtained by Aaltonen in [6, p.156]. The bound follows from
(31) and the following result
(x)
argmaxx∈[δ,θ] 1−αM RRW
= max{δ, (1 − 2/q)2 }.
x

(34)

The argmax above is not straightforward to obtain, and to quote from [6], was found by a mere chance.
The derivation is not presented in [6]. The purpose of this appendix is to i) record a proof of (34), and ii)
to prove that α̃M RRW (x) is ∪-convex. The author thanks Tero Laihonen for providing a copy of Aaltonen’s
work [6], which is not easily available.
p
p
Let ξ : [0, θ] → [0, θ] be the function defined by ξ(x) = ( θ(1 − x) − x(1 − θ))2 . We note that
αM RRW (x) = Hq (ξ(x)), and that ξ(x) decreases from θ to 0 as x runs from 0 to θ. It is easy to check
that ξ(ξ(x)) = x for x ∈ [0, θ]. Therefore we can invert the relation y = ξ(x) as x = ξ(y). We also note
that ξ((1 − 2/q)2 ) = 1/q. Therefore (34) is equivalent to the assertion:
q (y)
argmaxy∈[0,t] 1−H
= min{t, 1/q}.
ξ(y)

In terms of hA (y) :=

1−Hq (y)
ξ(y)

(35)

we must show
sign(h0A (y)) = sign(1/q − y),

y ∈ (0, θ).

q

q

A calculation shows that:
h0A (y)ξ(y)3/2

y(1−y)
θ(1−θ)

ln(q) =

q

y
1−θ

ln( yθ )

+

1−y
θ

ln( 1−y
) := G(y)
1−θ

Clearly sign(h0A (y)) = sign(G(y)). Therefore, we must show that sign(G(y)) = sign(1/q − y) for y ∈
(0, θ). Clearly G(1/q) = G(1 − θ) = 0. First we will prove that G(y) > 0 on [0, 1/q). We calculate:
r

p
− θ(1 − θ) G0 (y) =

Z
r

r

θ
y

Z

1−θ
1−y

ln(t)dt =

1

r

Z
1−θ
1−y

ln(t)dt +

θ
y

ln(t)dt.

1

We make the substitution t = 1/τ in the first integral to obtain:
r

p
− θ(1 − θ) G0 (y) =

Z
1

1−y
1−θ

r

ln(t)(1 −

1
)dt
t2

Z
+

r

θ
y

1−y
1−θ

ln(t)dt.

We note that t ≥ 1 in both the integrals, and hence both the integrands p
are non-negative.
Consequently,
p
the first integral is positive, and the second integral is also positive when θ/y > (1 − y)/(1 − θ). For
y ∈ [0, θ], this inequality is equivalent to (θ −y)(1−θ −y) > 0 which in turn is equivalentp
to y < 1−θ i.e.
0
y ∈ [0, 1/q). Thus, for y ∈ (0, 1/q), we have shown that G (y) < 0. Since G(0) = ln(q) q/(q − 1) > 0
and G(1/q) = 0, the fact that G(y) is strictly decreasing on [0, 1/q] implies G(y) > 0 on [0, 1/q).

14

Next we prove G(y) < 0 on (1/q, θ). Differentiating the expression for G0 (y) we get:
√
√
p
1−θ
θ
1−θ
4 θ(1 − θ) G00 (y) = ln( yθ ) y3/2
+ ln( 1−y
) (1−y)
3/2 .
Differentiating once more, we get:
p
4 θ(1 − θ) G000 (y) =

√

1−θ
(1
(1−y)5/2

1−θ
+ 23 ln( 1−y
)) −

√

θ
(1
y 5/2

+ 32 ln( yθ ))

√

θ
The second term − y5/2
(1 + 23 ln( yθ )) is negative on [1/q, θ) because θ/y > 1 on this interval. The first term
√

1−θ
(1 + 32
(1−y)5/2

1−θ
ln( 1−y
)) has the same sign as y − (1 − q −1 e2/3 ) for y ∈ [1/q, θ). It follows that G000 (y) < 0
for y ∈ [1/q, 1 − q −1 e2/3 ]. (We note that the condition for 1/q < 1 − q −1 e2/3 , is q ≥ 3, which is the case
here).
√
1−θ
1−θ
3
For y ∈ (1 − q −1 e2/3 , θ), as above (1−y)
5/2 (1 + 2 ln( 1−y )) is positive. It is also an increasing function of
y, because (1−θ)/(1−y) increases
with y. For y ∈ [1−q −1 e2/3 , θ], we note that θ/y decreases with y and
√
θ
θ/y ≥ 1. Therefore the term − y5/2 (1 + 23 ln( yθ )) increases with y. Thus G000 (y) is an increasing function of
y for y ∈ [1 − q −1 e2/3 , θ]. We note the boundary conditions on G000 (y): we have G000 (1/q) < 0 < G000 (θ).
To see this we note that

−4(θ(1 − θ))3 G000 (1/q) = 23 ln(q − 1)(θ3 + (1 − θ)3 ) + (θ3 − (1 − θ)3 ) > 0
because q > 2 is equivalent to θ > 1 − θ as well as ln(q − 1) > 0. Also
G000 (θ) =

2θ−1
4(θ(1−θ))2.5

> 0.

Since G000 (1 − q −1 e2/3 ) < 0 < G000 (θ) and G000 (y) is increasing on [1 − q −1 e2/3 , θ], we conclude that there
is a unique y0 in the interior of this interval such that G000 (y) has the same sign as y − y0 on this interval.
Together with the fact that G000 (y) < 0 on [1/q, 1 − q −1 e2/3 ], we obtain:
sign(G000 (y)) = sign(y − y0 )

on [1/q, θ].

This is illustrated in Figure 2, which shows the graphs of G(y) (dashed plot) and G000 (y) on [1/q, θ] for
q = 8. The point (y, G000 (y)) for y = 1 − q −1 e2/3 is marked. (In this plot, the values of G000 (y) are indicated
on the right-vertical axis, and the values of G(y) are indicated on the left-vertical axis). Thus G00 (y) is
decreasing on [1/q, y0 ] and increasing on [y0 , θ]. Since G00 (θ) = 0, it follows that G00 (y) < 0 on [y0 , θ).
We note that
G00 (1/q) = ln(q−1)(2θ−1)
> 0.
4(θ(1−θ))2
Thus G00 (1/q) > 0 > G00 (y0 ) together with the fact that G00 (y) is decreasing on [1/q, y0 ] implies that there
is a unique y1 in the interior of this interval such that G00 (y) has the same sign as y1 − y on this interval.
We have already shown that G00 (y) < 0 on [y0 , θ]. Thus we conclude
sign(G00 (y)) = sign(y1 − y)

on [1/q, θ).

This implies G0 (y) is increasing on [1/q, y1 ] and decreasing on [y1 , θ]. Since G0 (θ) = 0, we conclude that
G0 (y) > 0 on [y1 , θ). We note that
Z √q−1
G0 (1/q) = √ −1
ln(t)(1 − t12 )dt < 0.
θ(1−θ)

0

1

0

Since G (y) is increasing on [1/q, y1 ] and G (1/q) < 0 < G0 (y1 ), we conclude that there is a unique y2
in the interior of the interval [1/q, y1 ] such that G0 (y) has the same sign as y − y2 on this interval. Also
G0 (y) > 0 on [y1 , θ]. Thus we conclude:
sign(G0 (y)) = sign(y − y2 )

on [1/q, θ).

15

100

-0.02

0

-0.04

-100

-0.06

-200

-0.08

-300

-0.1

-400

-0.12

0.2

0.4

y

0.6

G000(y)

G(y)

0

-500

0.8

Fig. 2. Graphs of G(y) and G000 (y) on [1/q, θ] for q = 8.

This implies that G(y) is decreasing on [1/q, y2 ] and increasing on [y2 , θ]. Since G(1/q) = G(θ) = 0, we
see that G(y) is negative on (1/q, y2 ] as well as [y2 , θ). This finishes the proof of the assertion G(y) < 0
on (1/q, θ), and hence of (35).
0
Next, we prove the ∪-convexity of α̃M RRW (x). We must show that the derivative α̃M
RRW (x) is non2
decreasing. Since the derivative is constant on [0, (1 − 2/q) ], the problem reduces to showing that
αM RRW (x) is ∪-convex for x ∈ [(1 − 2/q)2 , θ]. This follows from the next lemma:
Lemma 6. The first MRRW bound αM RRW (δ) is ∪-convex if q = 2. For q > 2, it is ∩-convex on
[0, δM RRW ] and ∪-convex on [δM RRW , θ] where δM RRW satisfies:
1
2

√

−

q−1
q

< δM RRW < (1 − 2q )2 .

Proof: Let y = ξ(x). Let
χ(y) = 1 − 2y + (2θ − 1)
We calculate:
y 02
2y 00 y(1−y)

=

q

x(1−x)
θ(1−θ)

q

y(1−y)
θ(1−θ)

= χ(y)

(36)

p
Since x(1 − x)/(θ(1 − θ)) is non-negative, we also make the observation that that χ(y) > 0 for all
y ∈ [0, θ). Since αM RRW (x) = Hq (y), we get:
00
ln(q)αM
RRW (x) =

−y 02
y(1−y)

+ y 00 ln (q−1)(1−y)
.
y

Since ξ(ξ(x)) = x, we get y 0 = ξ 0 (x) = 1/ξ 0 (y). Using this we get:
00
0
2
αM
RRW (x)(ξ (y)) y(1 − y) ln(q) = −1 +

2y 00 y(1−y)
y 02

ln

q

(q−1)(1−y)
.
y

Using (36), we obtain:
r
00
0
2
αM
RRW (x)(ξ (y)) y(1

− y) ln(q) = −1 +

ln

(1−y)(q−1)
y
χ(y)

00
Let y ∈ (0, θ). We recall note χ(y) > 0 for y ∈ (0, θ). Thus for αM
RRW (x) has the same sign as
q
G2 (y) := ln( (1−y)(q−1)
) − χ(y).
y

16

We calculate:
G02 (y)y(1 − y) = χ(y)(y − 12 ).
Therefore, sign(G02 (y)) = sign(y − 1/2). In other words G2 (y) is decreasing on [0, 1/2] and increasing
on [1/2, θ). We note G2 (1/q) = ln(q − 1) − 2(1 − 2q ). The function
t 7→ ln(t − 1) − 2(1 − 2/t),
evaluates to 0 at t = 2, and is an increasing function of t for t ≥ 2 (because its derivative (1−2/t)2 /(t−1)
is positive). Thus G2 (1/q) > 0 for q > 2 and G2 (1/q) = 0 for q = 2. Since G2 (0) = +∞ and G2 (y)
is decreasing on [0, 1/q], we conclude that G2 (y) > 0 on [0, 1/q] if q > 2. If q = 2, then G2 (y) ≥ 0 on
[0, 1/q] = [0, θ]. In particular, for q = 2 the bound αM RRW (x) is ∪-convex on [0, θ].
√q−2 ).
q−1
√
2 t−1−t
<
4(t−1)3/2

For q > 2, we note that G2 (1/2) = 21 (ln(q − 1) −

The function b(t) = 12 (ln(t − 1) −

√t−2 )
t−1

satisfies b(3) = 12 (ln(2) − √22 ) < 0 and b0 (t) =
0 for t ≥ 3. Thus G2 (1/2) < 0 for all
q > 2. Since G2 (1/q) > 0 and G2 (1/2) < 0 and G2 (y) is decreasing on [1/q, 1/2], we conclude
that there is a yM RRW ∈ (1/q, 1/2) such that sign(G2 (y)) = sign(yM RRW − y) for y ∈ [0, 1/2]. Also
G2 (θ) = 0, G2 (1/2) < 0 and G2 (y) is increasing on [1/2, θ], which shows that G2 (y) < 0 on [1/2, θ). Thus
00
sign(G2 (y)) = sign(yM RRW − y) for y ∈ (0, θ). Since αM
RRW (x) has the same sign as G2 (y) (where
00
y = ξ(x)), we finally obtain sign(αM RRW (x)) = sign(x − δM RW W ) for
√ x ∈ (0, θ), where δM RW W =
1
ξ(yM RRW ) satisfies ξ(1/2) < δM RW W < ξ(1/q), or in other words: 2 − q−1
< δM RRW < (1 − 2q )2 . This
q
completes the proof of the lemma.
R EFERENCES
[1] R. Ahlswede and L. H. Khachatrian, “The diametric theorem in Hamming spaces—optimal anticodes,” Adv. in Appl. Math., vol. 20,
no. 4, pp. 429–449, 1998.
[2] M. Aaltonen, “A new upper bound on nonbinary block codes,” Discrete Math., vol. 83, no. 2-3, pp. 139–160, 1990.
[3] Y. Ben-Haim and S. Litsyn, “A new upper bound on the rate of non-binary codes,” Adv. Math. Commun., vol. 1, no. 1, pp. 83–92, 2007.
[4] P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Rep. Suppl., no. 10, pp. vi+97, 1973.
[5] T. Laihonen and S. Litsyn, “On upper bounds for minimum distance and covering radius of non-binary codes,” Des. Codes Cryptogr.,
vol. 14, no. 1, pp. 71–80, 1998.
[6] M. Aaltonen, “Bounds on the information rate of a tree code as a function of the code’s feedback decoding minimum distance,” Ann.
Univ. Turku. Ser. A I, no. 181, 1981.
[7] M. Tsfasman, S. Vlăduţ, and D. Nogin, Algebraic geometric codes: basic notions, ser. Mathematical Surveys and Monographs.
Providence, RI: American Mathematical Society, 2007, vol. 139.

