REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING
SPACES
PETER BOYVALENKOV † , DANYO DANEV

††

, AND MAYA STOYANOVA∗

arXiv:1801.01982v1 [cs.IT] 6 Jan 2018

Dedicated to the memory of Professor Vladimir Levenshtein (1935-2017)
Abstract. We develop refinements of the Levenshtein bound in q-ary Hamming spaces
by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. The first relevant cases are investigated
in detail and new bounds are presented. In particular, we derive generalizations and
q-ary analogs of a MacEliece bound. We provide evidence that our approach is as
good as the complete linear programming and discuss how faster are our calculations.
Finally, we present a table with parameters of codes which, if exist, would attain our
bounds.

Keywords. Error-correcting codes, Levenshtein bound, bounds for codes.
1. Introduction
Let Q = {0, 1, . . . , q − 1} be the alphabet of q symbols and H(n, q) be the set of
all q-ary vectors x = (x1 , x2 , . . . , xn ) over Q. The Hamming distance d(x, y) between
points x = (x1 , x2 , . . . , xn ) and y = (y1 , y2 , . . . , yn ) from H(n, q) is equal to the number
of coordinates in which they differ. A non-empty set C ⊂ H(n, q) is called a code.
The investigation of the connections between the codelength n, cardinality |C| and the
minimum distance d = d(C) = min{d(x, y), x 6= y ∈ C} is of great importance in Coding
Theory.
The spaces H(n, q) are sometimes considered as polynomial metric spaces (cf. [9,
14, 16]), where using ”inner” products hx, yi := 1 − 2d(x,y)
instead of distances is very
n
convenient. We define Tn = {t0 , t1 , . . . , tn }, where ti := −1 + 2i
n , i = 0, 1, . . . , n, as the
set of all possible inner products.
Let s ∈ Tn and
Aq (n, s) := max{|C| : C ⊂ H(n, q), s(C) ≤ s},
where s(C) = max{hx, yi, x 6= y ∈ C}, be the maximal possible cardinality of a code
in H(n, q) of prescribed maximal inner product s. In Coding Theory this quantity is
Date: January 9, 2018.
†
The research of this author was supported, in part, by a Bulgarian NSF contract DN02/2-13.12.2016.
††
The research of this author was supported, in part, by the Swedish Research Council (VR) and ELLIIT..
∗
The research of this author was supported, in part, by a Bulgarian NSF contract DN02/2-13.12.2016.
1

2

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

usually denoted by Aq (n, d), where s = 1 − 2d
n (= tn−d ) and d is the minimum distance
of C (so we have replaced the condition d(x, y) ≥ d by hx, yi ≤ s).
Levenshtein (cf. [14, 15, 16], see also [9]) developed theory and proved universal upper
bounds for Aq (n, s). In this paper we describe refinements of the Levenshtein bound that
can be applied for obtaining better bounds in the majority of the cases. Our refinements
have two major advantages – they are easy to derive and allow analytic investigation to
certain extent.
Improvements of the third Levenshtein bound in the binary case q = 2 were obtained
by Tietäväinen [25] and Krasikov-Litsyn [13], who developed bounds for d = n − n+j
2 ,
√
where 0 < j < 3 n. Earlier, in 1973, linear programming bounds were obtained by
McEliece (unpublished, see [18, Chapter 17, Theorem 38]) who proved the asymptotic
√
bound A2 (n, s) . (n − j)(j + 2), where 2d + j = n is as above, s = 1 − 2d
n , and j = o( n).
The McEliece bound was improved in [25] and [13] for j = o(n1/3 ).
On the other hand, binary codes of length n = (22m + 1)(2m − 1), size M = 24m and
minimum distance d = 22m−1 (2m −1) (so j = 2m −1) were constructed by Sidelnikov [22].
This shows that the McEliece bound is of the correct order of magnitude. We also note
that the maximum possible size of a code for j = 1 and n ≡ 1 (mod 4) is still unknown.
Much less is known in the q-ary case, where analogs of the Tietäväinen bound were
obtained in [19]. Our results give a generalization of the McEliece bound – first as we
prove it for every n ≥ q ≥ 2 and second, as we obtain its q-ary asymptotic analog.
This paper is organized as follows. In Section 2 we explain the general linear programming bound, the Levenshtein bound and related parameters. Section 3 is devoted to
general description of our refinements and discussion on its limits. We develop the first
relevant case giving a rigorous proof for the refinement of the third Levenshtein bound
in Section 4, where we also investigate the asymptotics of the new bounds. We also
provide evidence that our bounds for large enough nd = 1−s
2 are as good as the complete
linear programming despite being considerably simpler. Asymptotic bounds from the
refinement of the fourth Levenshtein bound are presented in Section 5. We also compile
a table of feasible parameters for good codes attaining our bounds.
2. Preliminaries
2.1. Krawtchouk polynomials and the linear programming framework. For
fixed n and q, the (normalized) Krawtchouk polynomials are defined by
1 (n,q)
K
(d),
ri i



P
(n,q)
i n
where d = n(1−t)
(d) = ij=0 (−1)j (q − 1)i−j dj n−d
2 , ri = (q − 1) i , and Ki
i−j are the
(usual) Krawtchouk polynomials that obey the three-term recurrent relation
(n,q)

Qi

(n,q)

K0

(t) :=

(n,q)

(d) = 1, K1

(d) = n(q − 1) − qd,

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

3

i + (q − 1)(n − i) − qd (n,q)
(q − 1)(n − i + 1) (n,q)
Ki
(d) −
Ki−1 (d), for i ≥ 1.
i+1
i+1
(n,q)
We point out that even if the Krawtchouk polynomials Ki
(d) are defined for all non(n,q)
negative integers i, the normalized polynomials Qi (t) are only defined for integers
i ∈ [0, n]. If f (t) ∈ R[t] is a real polynomial of degree m ≥ 0, then f (t) can be uniquely
P
(n,q)
(t).
expanded in terms of the Krawtchouk polynomials as f (t) = m
i=0 fi Qi
The next (folklore) assertion is the main source of linear programming bounds (aka
Delsarte bounds) for Aq (n, s).
(n,q)

Ki+1 (d) =

Theorem 2.1. Let n ≥ 2 and s ∈ [−1, 1) be fixed and f (t) be a real polynomial of degree
m such that:
(A1) f (t) ≤ 0 for every t ∈ Tn ∩ [−1, s];
P
(n,q)
(A2) the coefficients in the Krawtchouk expansion f (t) = m
(t) satisfy fi ≥ 0
i=0 fi Qi
for every i.
Then Aq (n, s) ≤

f (1)
f0 .

2.2. The Levenshtein bound. The so-called adjacent polynomials as introduced by
Levenshtein (cf. [16, Section 6.2], see also [14, 15]) are given by
(n−2,q)

(n−1,q)

(1)

(1,0,n,q)

Qi

K
(t) = Pii

j=0

K
(d − 1)
(1,1,n,q)
, Qi
(t) = Pi i

n
j
j=0
j (q − 1)

(d − 1)
,

(q − 1)j

n−1
j

(n−1,q)

(0,1,n,q)
Qi
(t)

=

Ki

n−1
i



(d)
,
(q − 1)i

where d = n(1 − t)/2.
For a ∈ {0, 1} and i ∈ {1, 2, . . . , n − 1}, denote by t1,a
i the greatest zero of the adjacent
(1,a,n,q)
1,1
polynomial Qi
(t) (see (1)) and also define t0 = −1 as well as tn1,0 = 1. We have
1,1
1,0
the interlacing properties t1,1
k−1 < tk < tk , see [16, Lemmas 5.29, 5.30]. For a positive
integer m = 2k − 1 + ε, ε ∈ {0, 1}, let

h
1,ε
.
,
t
Im := t1,1−ε
k−1+ε k
2n−1
Then the set of well defined intervals {Im }m=1
forms a partition of the interval [−1, 1)
into non-overlapping subintervals. For every s ∈ Im , Levenshtein used Theorem 2.1 with
certain polynomials of degree m

(2)

(n,s,q)
fm
(t) = (t − s)(t + 1)ε A2 (t)
(n,s)

(see [16, Equations (5.81) and (5.82)]), where deg(fm
tions (6.45) and (6.46)])

(1,1−ε,n,q)

(3)

Aq (n, s) ≤ Lm (n, s; q) = q

1−ε

1−

Qk−1

) = m, to obtain (see [16, Equa-

(s)

(0,ε,n,q)
Qk
(s)

! k−1+ε  
X n
j=0

j

(q − 1)j

4

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

for every s ∈ Im . The bound (3) is attained by many codes with good combinatorial
properties but is weak in many other particular cases. It is also worth to mention its
good asymptotic behavior (see [3], [16, Section 6.2]).
In [6] two of the authors obtained (for any q) and investigated (for q = 2) necessary
and sufficient conditions for global optimality of the Levenshtein bounds (see also [16,
Theorem 5.47]). Here we discuss another possibility of improving Levenshtein bounds by
taking into account the discrete nature of the set of inner products.
3. Our refinement – vanishing at inner products instead of zeros of the
Levenshtein’s polynomial
The roots −1 ≤ α0 < α1 < · · · < αk−2+ε < αk−1+ε = s of the Levenshtein polynomials
(n,s,q)
fm
(t) (we recall that m = 2k − 1 + ε, ε ∈ {0, 1}) are exactly the roots of the equation
(t + 1)ε [Pk (t)Pk−1 (s) − Pk (s)Pk−1 (t)] = 0,

(4)

(1,ε,n,q)

where Pi (t) = Qi
(t) ∈ Q[t]. Since (4) is equivalent to an equation with integer
coefficients, the double zeros αi , i = ε, . . . , k −2+ε, will rarely coincide exactly with inner
products from the set Tn . Taking this into account we obtain the following refinement of
the Levenshtein bound.
We first locate the nodes αi , i = ε, . . . , k − 2 + ε, with respect to the elements (the
inner products) of Tn . Then, if αi ∈ (tj−1 , tj ) for some integer j ∈ [1, n], we replace the
double zero αi by two simple zeros1 γ2(i−ε)+1 = tj−1 and γ2(i−ε+1) = tj . After setting
γ2k−1 = s, we define the polynomial
f (t) = (t + 1)

ε

2k−1
Y

(t − γi )

i=1

of degree m = 2k − 1 + ε. We observe that the values of this polynomial in the interval
(tj−1 , tj ) are positive and, in particular, f (αi ) ≥ 0, with (very rare apart from αk−1+ε =
s ∈ Tn ) equality case if and only if αi = tj . Finally, in the case when the degree
m exceeds the codelength n we reduce the polynomial f (t) to its remainder from its
n
Y
division by g(t) =
(t − ti ). This operation is standard when the polynomial metric
i=0

space (PMS) is finite.
This construction clearly implies that the condition (A1) is satisfied. Moreover, using
the quadrature formula
(5)

f0 =

k−1+ε
X
1
+
ρi f (αi )
Lm (n, s; q)
i=0

1In the special case α = t for some i = ε, . . . , k − 2 + ε and j there are two possible replacements of
i
j
αi – by tj−1 and tj or by tj and tj+1 . Our choice is simple – we check both and take the better one.

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

5

(see [16, Theorem 5.39]) and the inequalities f (αi ) ≥ 0 we conclude that f0 > 0 always
follows.
The condition (A2) for i ≥ 1 can be easily checked numerically in every particular case,
and it is satisfied in the great majority of the cases we considered. We give a rigorous
proof for the case m = 3 below.
Summarizing, whenever we have (A2), Theorem 2.1 gives upper bound for the corresponding Aq (n, s). Clearly, this is a strict improvement of the Levenshtein bound (3)
if and only if αi 6∈ Tn for at least one i. Note that αi ∈ Tn occurs very rare – this is
connected to integral zeros of Krawtchouk polynomials (see [12, 23]).
Our numerical results cover wide range of values of q, n and s, as we inspect all feasible
s for given q and n. Unfortunately, comparisons with well established sources such as
[7, 1, 4] can be made in small range, namely, for alphabet size q = 2, 3, 4, and 5, and for
lengths n ≤ 28, n ≤ 16, n ≤ 12, and n ≤ 11, respectively. In these ranges we recover the
following best known upper bounds
A3 (14, −1/7) ≤ 237, A4 (11, −3/11) ≤ 320, A5 (11, −5/11) ≤ 250
(the Levenshtein bounds are 256.5, 364, and 265, respectively).
It is clear that, in every particular case, the numerics from our refinements can not be
better than the complete (integer) linear programming (see, for example [26]). However,
we are going to show strong evidence that for every fixed m, our method gives the
same results as the complete linear programming gives for large enough n despite being
considerably simpler for computation.
The much easier computation allows us to go for large lengths. Bounds for large lengths
were numerically investigated (for binary codes only) by Barg-Jaffe [2]. Our computational results agree well with their application of the simplex method for large nd = 1−s
2 .
1
We give a short table for comparison. The bounds are computed for n log2 A2 (n, s).
Table 1. Bounds for binary codes, n = 1000,

d
n

=

1−s
2

∈ [0.25, 0.45].

d/n
0.25
0.3
0.35
0.4
0.45
Lm (n, s; 2)
0.387 0.283 0.191 0.115 0.505
our bound
0.386 0.281 0.188 0.110 0.047
simplex from [2] 0.380 0.280 0.188 0.109 0.047
This comparison and our computational results for larger q lead us to the conjecture
that our method matches the best results possible by Theorem 2.1 for large enough ratio
d/n = (1 − s)/2.
Conjecture 3.1. For a fixed q ≥ 3 there exist a constant sq such that whenever s ∈
[−1, sq ) ∩ Tn (that is large enough d/n = (1 − s)/2) the above refinements are the best
that can be obtained by Theorem 2.1.

6

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

In order to support this conjecture, in Figure 1 we present graph for the function sq (n)
defined as the range [−1, sq (n)) ∩ Tn where our improvement is optimal in the sence of
Theorem 2.1.
MyTitle

1

q3

0.8

q5
q10

0.6

0.4

s

0.2

0

-0.2

-0.4

-0.6

-0.8

-1
50

100

150

200

250

300

350

400

450

500

n

Figure 1. The function sq (n) for some q’s and codelengths n ∈ [3, 500].
We note also that, similarly to [2], our computations do not support the conjecture of
Samorodnitsky [20] on the exponential strength of the linear programming method.
Semidefinite programming was shown to be better than the linear programming in
most particular cases (see, for example, [10, 21, 17]) but it hardly gives bounds in analytic
forms. So we see another advantage in giving analytic form of our bounds in the first
cases (see the next sections).
4. The refinement of L3 (n, s; q)
In this section we apply our refinement in the case of the third Levenshtein bound.
We provide proof for the feasibility of the chosen polynomial as well as some numerical
results for the global optimality of this polynomial.
4.1. Proof of the feasibility of suggested polynomial. Let us set2
(6)

d=n−1−

n−2+j
,
q

where the parameter j will be explained below. We proceed with the general case of
upper-bounding Aq (n, s) in the range
h
  (q − 2)(n − 2) (q − 2)(n − 2) S − q 
1
1,1 1,0
s ∈ I3 = t1 , t2
,−
+
,
= −
nq
nq
nq
2This convention is natural extension of McEliece’s d = (n − j)/2 used for q = 2.

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

p
q 2 + 4(q − 1)(n − 2). Since d = n(1 − s)/2, we obtain the ranges for d and

where S1 =
j to be

(7)

d∈

7

n−2
n − 2 S1 − q
−
, (n − 1) −
(n − 1) −
q
2q
q





S1 − q
⇐⇒ j ∈ J3 = 0,
2


.

The simple form of J3 justifies the change of the variable.
In the particular case of m = 3 the polynomial defined in (2) becomes
(n,s,q)

f3
where s = α1 = 1 −

2d
n

(t) = (t − α0 )2 (t − s) = (t − α0 )2 (t − α1 ) ,

= −1 +

2(n−2+j+q)
nq

2j(n−1)
nq(j+q−1) , since α0 and s are
j(n−1)
0)
set d0 = n(1−α
= n − q(j+q−1)
2

and α0 = −1 +

the roots of the equation (4) for k = 2 and ε = 0. Let us
and define e to be the unique rational number in the interval (0, 1] such that d0 + e is
integer. We point out that


2(d0 + e)
2(d0 + e − 1)
α0 ∈ 1 −
,1 −
n
n
r
and that e = q(j+q−1)
, where r is the positive remainder from the division of j(n − 1) by
q(j + q − 1), i.e. r ≡ j(n − 1) (mod q(j + q − 1)) and r ∈ (0, q(j + q − 1)] ∩ Z.
Now we are in a position to define our improving polynomial as

f (t) =
(8)

=

=







2(d0 +e)
t − 1 + 2(d0 +e−1)
(t − s)
n
n



2j(n−1)
2(e−1)
2j(n−1)
t + 1 + 2e
−
t
+
1
+
−
n
n
nq(j+q−1)
nq(j+q−1) ×


2(n−2+j+q)
t+1−
nq
(n,q)
(n,q)
(n,q)
f0 + f1 Q1 (t) + f2 Q2 (t) + f3 Q3 (t),

t−1+

where the coefficients fi , i = 3, 2, 1, 0, are given by
f3 =
(9)

f2 =

(10)

f1 =
f0 =

8(q − 1)3 (n − 2)(n − 1)
> 0,
q 3 n2
8(q − 1)2 (n − 1)A
,
q 3 n2 (q + j − 1)

8(q − 1) (eq − B)2 + C
,
q 3 n2

8 a2 (2 − q − j) + Da + E
> 0,
q 3 n3

8

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

for
A = −j 2 + (2eq − 1)j + (q − 1)(2n + 2eq + q − 4),
h
i
1
q
B =
j(j − 2) − n(q − 1) + (3j + q − 1) ,
j+q−1
2
q2
C = −j 2 + (−q + 2)j + (3n − 2)(q − 1) − ,
4
D = (j + q − 1)[2n(q − 1) − q] + q,
E = −n(n − 1)(q − 1)2 (j + q),
(n − 1)(q − 1)(q + j)
a =
+ eq.
q+j−1
We proceed with the proof of the positivity of the coefficients f1 and f2 .
Lemma 4.1. We have f2 > 0 for every n ≥ 2 and q ≥ 2.
Proof. It follows from (9) that it is enough to prove that A > 0. Observing that A is a
concave quadratic function in j, according to (7) we have to check the positivity of A for
j = 0 and j = S12−q , respectively. For the former we have
A = (q − 1)(2n + 2eq + q − 4) ≥ (q − 1)(2n + q − 4) > 0
and for the latter


q−1
(2n + q − 4)(q − 1)
A = eq +
S1 + eq(q − 2) +
> 0,
2
2
whenever n ≥ 2 and q ≥ 2.



Lemma 4.2. We have f1 > 0 for every n ≥ q ≥ 2.
Proof. According to (10) it is sufficient to show that C > 0. As in the proof of Lemma
4.1, we observe that C is a concave quadratic function of j so we check its values at the
limits of the interval J3 . We obtain those to be
(3n − 2)(q − 1) −

q2
q2
q
≥ (3q − 2)(q − 1) −
= 2 + (11q − 20) > 0
4
4
4

and

q
S1 + 2n(q − 1) − q − q 2 /4 ≥ S1 + (7q − 12) > 0,
4
whenever n ≥ q ≥ 2.



Remark 4.3. Our numerics suggest that we might always have f2 > f1 > f0 . Since
f0 > 0 follows by the formula (5), another proof of the positivity of f1 and f2 could
probably be done along these lines.
Theorem 4.4. We have
(11)

Aq (n, s) ≤

a(a + q)dq
,
a2 (2 − q − j) + Da + E

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

9

where the parameters are determined as above.
Proof. The condition (A1) is obviously satisfied by our improving polynomial. The condition (A2) is satisfied as well – Lemmas 4.1 and 4.2 give f2 ≥ 0 and f1 ≥ 0, respectively, f3 > 0 is obvious, and f0 > 0 follows, as mentioned above, from (5). Therefore
and simplifications give the desired bound.

Aq (n, s) ≤ ff(1)
0
Example 4.5. For q = 4, n = 11 and s = −3/11 (this s corresponds to minimum distance
d = n(1−s)/2 = 7) we are in the range of the third Levenshtein bound L3 (11, s; 4). Since
17
9
7
3
α0 = − 22
∈ − 11
, − 11
and α1 = s = − 11
, we have our improving polynomial as follows:




7
3
9
t+
t+
f (t) =
t+
11
11
11
63 (11,4)
117 (11,4)
45 (11,4)
1215 (11,4)
=
Q0
(t) +
Q1
(t) + Q2
(t) +
Q
(t)
5324
484
44
484 3
and A4 (11, −3/11) ≤ ff(1)
= 320 (here L3 (11, −3/11; 4) = 364). The best known lower
0
bound in this case is A4 (11, −3/11) ≥ 128 (see [7]). Further analysis via the distance
distributions of a putative quaternary (11, 320, −3/11) code C does not give a contradic3
7
9
tion. Indeed, all possible inner products of C are − 11
, − 11
and − 11
and such a code
must be distance regular, i.e. every point of C has the same distance distribution, which
turns out to be integral.
We now calculate the asymptotic form of the bound from Theorem 4.4.
Corollary 4.6. Let j = cnα ∈ J3 for some positive constant c and some α ∈ [0, 1/2].
The behavior of the upper bound given by (11) as n → ∞ is as follows
(12)
(13)

Aq (n, s) ≤ [(q − 1)n − (j + q − 2)](j + q) + j(j + q − 1)2 + o(1), α ∈ [0, 1/5),
Aq (n, s) ≤ (q − 1)(q + j)n + j 3 +

c5 n5α−1
+ o(n), α ∈ [1/5, 1/2),
q−1

and
(14) Aq (n, s) ≤

c(q − 1)2 3/2 (q − 1)(c4 − (q − 1)(3c2 − q 2 + q))
n +
n + o(n), α = 1/2.
q − 1 − c2
(q − 1 − c2 )2

Proof. The upper bound in (11) can be re-written as
(15)

Aq (n, s) ≤ [(q − 1)n − (j + q − 2)](j + q) + j(j + q − 1)2
[(q − 1)n + (eq + 1)(eq + 1 − q)]j 6 + Pq,e,n (j)
+
,
(q − 1)2 (j + q)n2 + Qq,e,n (j)

where Pq,e,n (j) and Qq,e,n (j) are polynomials in j of degrees 5 and 3, respectively, and
with coefficients that are linear in n. We notice that for the fraction in (15), the nominator
is of order Θ(n1+6α ) and that the denominator has the order Θ(n2+α ) for all α ∈ [0, 1/2].
This gives the result in (12) since 1 + 6α < 2 + α when α ∈ [0, 1/5).

10

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

To obtain (13), we observe that for large n the nominator behaves like (q − 1)nj 6 +
Θ(n1+5α ). For all α ∈ [1/5, 1/2) we have 1 + 5α − (2 + α) < 1 and also iα < 1, for
i = 0, 1, 2. Now (13) follows by ignoring the terms of orders in n that are less than 1.
√
Finally, by substituting j = c√ n in (15) and performing polynomial division for the

polynomials in the variable x = n we arrive at (14).
4.2. On Conjecture 3.1 for m = 3. We reformulate the linear programming bound
back to its classical form (see [8, Sections 3.2 and 3.3], [9, Section 3B], [15, Corollary
2.7]).
P
(n,q)
(z) satisfies the conditions
Theorem 4.7. Let the polynomial g(z) = ni=0 gi Ki
g0 > 0, gi ≥ 0, i = 1, 2, . . . , n;
g(0) > 0, g(i) ≤ 0, i = d, d + 1, . . . , n.
Then Aq (n, s) ≤ g(0)/g0 , where s = 1 − 2d/n.
In the light on Theorem 4.7 the best upper bound on the quantity Aq (n, s) is obtained
(n,q)
P
P
Ki
(z) ∗
x∗ (n,q)
by the polynomial g ∗ (z) = 1 + ni=1 rii Ki
x for which the
(z) = 1 + ni=1 (q−1)
i n
(i) i
coefficients x∗ = (x∗1 , x∗2 , · · · , x∗n ) constitute a solution to the linear optimization problem
x1 + x2 + · · · + xn
n
(n,q)
X
Kl
(i)
subject to
xl ≤ −1, i = d, (d + 1), . . . , n
rl
l=1
xl ≥ 0,
l = 1, 2, . . . , n.
minimize
(16)

Applying the KKT optimality conditions (see for example [5, Section 5.5]) we can
conclude that necessary and sufficient condition for x∗ to be optimal is the existence of
numbers λl , l = 1, 2, . . . , n, and µi , i = d, d + 1, . . . , n, such that
λl = 1 +
(17)

λl x∗l = 0,
µi g ∗ (i) = 0,
µi ≥ 0,

n
X
i=d

(n,q)

µi

Kl

rl

(i)

≥ 0, l = 1, 2, . . . , n,
l = 1, 2, . . . , n,
i = d, (d + 1), . . . , n,
i = d, (d + 1), . . . , n.

Equation (17) turns out to be a very powerful tool for checking the global optimality of
a given polynomial. In particular, if we have a polynomial f (t) of degree m that satisfies
conditions (A1) and (A2) of Theorem 2.1 and has m different roots in the interval [−1, s],
then we can exactly determine the numbers µi , i = d, d + 1, . . . , n, if the Krawtchouk
expansion of f (t) in (A2) has strictly positive coefficients. The polynomial f (t) would
then be globally optimal if and only if all the lambdas, λl , l = 1, 2, . . . , n, calculated as

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

11

in (17) are non-negative. Our approach for improving the Levenshtein bound very often
results in such polynomials.
Let us now
 consider the polynomial f (t) as defined by (8) and let us set g(z) =
1
2z
f
1
−
f0
n . We can easily verify that
(18)

g(z) = 1 +

3
(n,q)
X
(z)
fi Ki
.
f0
ri
i=1

We now determine the Lagrange multipliers λ∗i and µ∗i for the polynomial defined in (18).
It has already been shown that fi > 0, i = 0, 1, 2, 3, which according to (17) means that
λ∗i = 0, i = 1, 2, 3. Since g(i) = 0 only for i ∈ {d, d0 + e − 1, d0 + e} we have µ∗i = 0 for all
i ∈ {d + 1, d + 2, . . . , n} \ {d0 + e − 1, d0 + e}. The remaining three µ∗i ’s can be obtained
from the system of linear equations
(n,q)

(19) µ∗d

Kl

rl

(d)

(n,q)

+ µ∗d0 +e−1

Kl

(n,q)

(d0 + e − 1)
K
+ µ∗d0 +e l
rl

(d0 + e)
= −1, l = 1, 2, 3.
rl

The system (19) has an unique solution (µ∗d , µ∗d0 +e−1 , µ∗d0 +e ) with help of which we can
calculate the remaining λ∗i , for i = 4, 5, . . . , n, according to
(n,q)

(n,q)

(n,q)

(d0 + e − 1)
K
(d0 + e)
+ µ∗d0 +e i
.
ri
ri
ri
The first step towards the calculation of the lambdas is the following statement.
(20)

λ∗i = 1 + µ∗d

Ki

(d)

+ µ∗d0 +e−1

Ki

Lemma 4.8. The weights (µ∗d , µ∗d0 +e−1 , µ∗d0 +e ) that solve system (19) can be calculated
as
n(q − 1)CD[C + q(j + q − 1)]
µ∗d =
,
AB[B + q(j + q − 1)]
en(q − 1)E[C + q(j + q − 1)]
µ∗d0 +e−1 =
,
AB
(1 − e)n(q − 1)CE
µ∗d0 +e =
,
A[B + q(j + q − 1)]
where
A = −(q + j − 2)[eq(j + q − 1)]2 + (n − 1)(q − 1)(j + q)[n(q − 1) − j(q + j − 2)]
+eq(j + q − 1)[(q 2 + jq − q − 2j)(q + j − 2) + 2n(q − 1)],
B = (n − 2 + j)(q − 1) + j(j − 1) + eq(j + q − 1),
C = (n − 1)(q − 1)(j + q) + eq(j + q − 1),


h
q i2
q2
2
D = (n − 1)(q − 1) + (2e − 1)(j + q − 1)
+ (j + q − 1) (n − 1)(q − 1) −
,
2
4
E = (j + q − 1)3 [(n − 1)(q − 2) + n − j].

12

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

Proof. Direct check shows that the above defined µ∗d , µ∗d0 +e−1 and µ∗d0 +e satisfy (19) for
any n, q, e ∈ (0, 1], j ∈ J3 and l = 1, 2, 3.

The non-negativity of µ∗d , µ∗d0 +e−1 and µ∗d0 +e for n ≥ q ≥ 2, j ∈ J3 and any e ∈ [0, 1)
can be derived from Lemma 4.8 by showing the positivity of the parameters A, B, C, D
and E. Obviously B > 0 and C > 0 with the only exception of the trivial case n = q = 2,
e = j = 0 for which B = 0. The parameter D is positive since (n − 1)(q − 1) ≥ (q − 1)2 ≥
(q/2)2 whenever n ≥ q ≥ 2 with equality only for n = q = 2. As A is a quadratic
function in e with negative leading coefficient, its positivity for e ∈ [0, 1) can be checked
by investigating the values for e = 0 and e = 1. For these values we have (n−1)(q −1)(j +
q)[n(q − 1) − j(q + j − 2)] and [(n(q − 1) + q + 1)j + (n + 1)q(q − 1)][n(q − 1) − j(q + j − 2)],
respectively. For any j ∈ J3 we have
n(q − 1) − j(q + j − 2) ≥ n(q − 1) −

S1 − q
S1 − q
(q +
− 2) = (q − 2) + S1 > 0,
2
2

which shows the positivity of A. Finally, the positivity of E follows from the fact that
(n − 1)(q − 2) + n > (S1 − q)/2 ≥ j.
We summarize the above observations into the following result.
Theorem 4.9. Let f (t) be the third degree polynomial given in (8) and let λ∗i , for i =
4, 5, . . . , n, be given by (20), where the triple (µ∗d , µ∗d0 +e−1 , µ∗d0 +e ) is defined as the unique
solution to the linear equation system (19). Then if λ∗i ≥ 0 for every integer i ∈ [4, n],
the bound (11) on Aq (n, s) is the best one that can be obtained by the linear programming
method described in Theorem 2.1.
The above statement is a powerful tool for checking the global optimality of the suggested polynomial in the case of the third Levenshtein bound. A similar result can be
obtained for the cases when the bound of higher order is valid. However, in those cases
the non-negativity of the µ∗j ’s is not always true and thus has to be added to the nonnegativity condition on the λ∗i ’s. Some observations in this directions are provided in the
next section.
Our numerical results suggest that Theorem 4.9 is applicable in all cases with very few
exceptions. We have been able to verify that for codelengths n up to 1000 and alphabet
sizes in the range 3 ≤ q ≤ 10, the only cases when the suggested polynomial does not
provide the optimal linear programming bound are for q = 3 and n ∈ {5, 7, 8, 9}.

5. Refinements of L4 (n, s; q) and L5 (n, s; q)
The Levenshtein bound Aq (n, s) ≤ L4 (n, s; q) is valid in the range
h
  S − (q − 2)(n − 2) − q S − (q − 2)(n − 3) 
1
2
1,0 1,1
s ∈ I4 = t2 , t2
=
,
,
nq
nq

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

13

p
where S1 is as above and S2 = q 2 + 4(q − 1)(n − 3), n ≥ 3. Then


n − 3 q + S2
n − 2 S1 − q
d ∈ D4 = n − 1 −
−
,n − 1 −
−
q
2q
q
2q


S1 − q S2 + q
⇐⇒ j ∈ J4 =
,
−1 .
2
2
The polynomial from (2) is
(n,s,q)

f4

(t) = (t + 1)(t − α1 )2 (t − s) = (t − α0 )(t − α1 )2 (t − α2 ),

2(n−2+j+q)
where s = α2 = 1 − 2d
again, α1 = − (n−2)(j(q−2)+2(q−1))
, and α0 = −1
n = −1 +
nq
nqj
(α1 and s are the roots of the equation (4) for k = 2 and ε = 1).
1)
We set d0 = n(1−α
= n−1− (j−q+1)(n−2)
and define e to be the unique rational number
2
qj
in the interval (0, 1] such that b := d0 + e is integer. Then our improving polynomial is


2(b−1)
t
−
1
+
(t − s)
f (t) = (t + 1) t − 1 + 2b
n
n
(21)
(n,q)
(n,q)
(n,q)
(n,q)
= f0 + f1 Q1 (t) + f2 Q2 (t) + f3 Q3 (t) + f4 Q4 (t),

The positivity of the coefficients f1 , f2 and f3 can be approached like in the previous
section but we prefer to omit the cumbersome calculations and to go directly to an
asymptotic.
Theorem 5.1. Provided fi ≥ 0 for i = 1, 2, 3, 4, we have
Aq (n, s) ≤

q 3 b(b − 1)(n(q − 1) − j − q + 2)
,
(1 − j)q 2 b2 + C1 qb − C2

where b and j are determined as above, C1 = j(q − 1)(2n − 1) + j − q, and C2 =
(q − 1)(n − 1)[(q − 1)(j + 1)n + 2(j − q + 1)].
Proof. Under the assumptions, the polynomial f (t) satisfies the conditions of Theorem
2.1. Thus it is enough to compute f (1) and f0 and to plug in f (1)/f0 .

We are not aware of improvements of the fourth Levenshtein bound in the spirit of
the discussion from the previous section. We proceed with an analog of the McEliece
J4 is short and we can express j as j = S12−q + c, where c ∈
hbound. The
 interval 
0, (q − 1) 1 −

2
S1 +S2

is some constant. Note that c ∈ [0, q − 1).

Theorem 5.2. For any s =
have
(22)

S1 −n(q−2)+2c+q−4
nq

Aq (n, s) .

h

∈ Tn and c ∈ 0, (q − 1) 1 −

q(q − 1)2 n2
as n → ∞.
2(q − c)

2
S1 +S2



we

14

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

h

Proof. For large n and c ∈ 0, (q − 1) 1 −

f4 > 0, f3 ∼

2
S1 +S2



, we have

16(q − 1)3
16(q − 1)2.5
32(q − 1)2
>
0,
f
∼
>
0,
f
∼
> 0.
2
1
q4
q 4 n0.5
q4n

Therefore (A1) and (A2) are satisfied and Aq (n, s) . f (1)/f0 . The calculation of the
asymptotic of f (1)/f0 now gives (22).


The analytical investigation of the refinement of the fifth Levenshtein bound L5 (n, s; q)
seems technically quite difficult. It is convenient, however, to illustrate the computational
strength of our method – we are able to reach lengths 10000 (for q = 3) in about 30
minutes of computations on an Intel Core2 Duo P9300 @ 2.26GHz processor. For any
fixed n we compute all bounds in the range of L5 (n, s; 3), which amounts to 225654 cases
in the codelength range 6 ≤ n ≤ 10000. The computations include verification of the
fact that fi ≥ 0 for i = 1, 2, 3, 4, 5. With no exception, the requirement (A2) in Theorem
2.1 has been satisfied.
Finally, we note that the refinement of L5 (n, s; q) is attained asymptotically (since
the Levenshtein bound L5 (n, s; q) itself is attained) by the Kerdock
of length
√ codes [11]
2`−1
2`
2
4`
− 2`−1 .
n = 2 , cardinality M = n = 2 and minimum distance d = (n − n)/2 = 2

6. Parameters of putative codes attaining our bounds
In the table below, we list all codes which would attain, if exist, our refinement of the
third Levenshtein bound L3 (n, s), in the range n ≤ 100 for the lengths and 2 ≤ q ≤ 5
for the alphabet size. The bound L3 (n, s) is shown in the fourth column. The sixth
column contains the roots of our polynomials, i.e. the only three possible inner products
of attaining codes, and the last column gives the distance distribution of such codes
(ordered accordingly to the inner products). The cases where the best known upper
bound from [7] is repeated are marked with asterisk.
The putative optimal codes must be 3-designs and this allows one to compute their
distance distribution. Of course, if the distance distributions is not integral, such code
does not exist. For lengths n ≤ 300, there are 7 out of 38 (for q = 2), 14 out of 54
(for q = 3), 20 out of 47 (for q = 4), and 18 out of 39 (for q = 5) cases which pass the
integrality test. Extended version of the table will be uploaded on the Internet.
Table 2. Parameters for attaining the refinement of L3 (n, s), n ≤ 100, 2 ≤ q ≤ 5

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

q
n
2 12
2 56
2 90
2 96
*3
4
3
7
3 20
3 25
3 27
3 40
3 52
3 88
4
4
*4
5
4
8
4
9
*4 11
4 13
4 18
4 42
4 49
4 56
*5
4
*5
5
*5
6
5
9
*5 11
5 16
5 21
5 25
5 45
5 55
5 72
5 75
5 91
5 92
5 100

d L3 (n, s) Refinement
5
62.50
60
25
1135
1100
41 2863.69
2788
45
1161
1155
2
33
27
4
57
54
12 312.429
306
15
531
513
16
874
840
24
2421
2349
32
2094
2052
55
5745
5670
2
83.20
64
3
76
64
5
182.50
160
6
136
128
7
364
320
9
196
192
12
697.6
640
30 1190.59
1184
35
1660
1640
39 7676.5
7176
2
167.86
125
3
191.67
125
4
145
125
6
485
375
8
265
250
12
385
375
16
505
500
18
3621
3645
34
3649
3250
42 3705.8
3675
56 3257.26
3250
57 12141
11970
70
9725
9625
70 26339.3
25025
76 55841
55195

Inner products
−1/2, −1/3, −1/6
−5/28, −1/7, 3/28
−2/15, −1/9, 4/45
−1/6, −7/48, 1/16
−1, −1/2, 0
−1, −5/7, −1/7
−7/10, −3/5, −1/5
−3/5, −13/25, −1/5
−5/9, −13/27, −5/27
−1/2, −9/20, −1/5
−1/2, −6/13, −3/13
−5/11, −19/44, −1/4
−1, −1/2, 0
−1, −3/5, −1/5
−1, −3/4, −1/4
−1, −7/9, −1/3
−9/11, −7/11, −3/11
−1, −11/13, −5/13
−7/9, −2/3, −1/3
−16/21, −5/7, −1/7
−5/7, −33/49, −1/7
−9/14, −17/28, −11/28
−1, −1/2, 0
−1, −3/5, −1/5
−1, −2/3, −1/3
−1, −7/9, −1/3
−1, −9/11, −5/11
−1/ − 7/8, −1/2
−1, −19/21, −11/21
−19/25, −17/25, −11/25
−7/9, −11/15, −23/45
−43/55, −41/55, −29/55
−29/36, −7/9, −5/9
−53/75, −17/25, −39/75
−5/7, −9/13, −49/91
−16/23, −31/46, −12/23
−17/25, −33/50, −13/25

15

Distance distribution
5, 15, 39
175, 275, 649
492, 697, 1598
90, 252, 812
6, 8, 12
4, 14, 35
16, 85, 204
114, 75, 323
272, 84, 483
928, 144, 1276
608, 208, 1235
1925, 440, 3304
21, 24, 18
18, 15, 30
15, 60, 84
16, 27, 84
99, 55, 165
9, 39, 143
135, 144, 360
36, 259, 888
205, 245, 1189
1287, 2093, 3795
52, 48, 24
44, 40, 40
44, 24, 60
44, 162, 168
40, 44, 165
30, 64, 280
16, 84, 399
1638, 132, 1694
429, 792, 2028
132, 1078, 2464
64, 585, 2600
4617, 608, 6744
2695, 780, 6149
7084, 4784, 13156
26809, 912, 27473

References
[1] E. Agrell, A. Vardy, K. Zeger, A table of upper bounds for binary codes, IEEE Trans. Inform. Theory
47, 2001, 3004-3006.
[2] A. Barg, D. Jaffe, Numerical results on the asymptotic rate of binary codes, Codes and Association
Schemes (A. Barg and S. Litsyn, eds.), DIMACS series, vol. 56, AMS, Providence, R.I., 2001, 25-32.

16

P. BOYVALENKOV, D. DANEV, AND M. STOYANOVA

[3] A. Barg, D. Nogin, Spectral approach to linear programming bounds on codes, Problems of Information Transmission 42(2), 2006, 77-89.
[4] M. R. Best, A. E. Brouwer, F. J. MacWilliams, A. M .Odlyzko, N. J. A. Sloane, Bounds for binary codes
of length less than 25, IEEE Trans. Inform. Theory 24, 1978, 81-93.
[5] S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
[6] P. Boyvalenkov, D. Danev, On linear programming bounds for codes in polynomial metric spaces,
Probl. Inform. Transm. 34, No. 2, 1998, 108-120.
[7] A. E. Brouwer, Tables of codes, http://www.win.tue.nl/∼aeb/
[8] P. Delsarte, An Algebraic Approach to the Association Schemes in Coding Theory, Philips Res. Rep.
Suppl. 10, 1973.
[9] P. Delsarte, V. I. Levenshtein, Association schemes and coding theory, Trans. Inform. Theory 44, 1998,
2477-2504.
[10] D. Gijswijt, A. Schrijver, H. Tanaka, New upper bounds for nonbinary codes based on the Terwilliger
algebra and semidefinite programming, J. Combin. Theory, Ser. A, 113, 1719-1731, 2006.
[11] A. M. Kerdock, A class of low-rate nonlinear binary codes, Inform. and Control 20, 182-187, 1972.
[12] I.Krasikov, S.Litsyn, On integral zeros of Krawtchouk polynomials, Journal of Combinatorial Theory,
Ser. A, 74(1), 1996, 71-99.
[13] I.Krasikov, S.Litsyn, Linear programming bounds for codes of small codes, Europ. J. Comb. 18,
1997, 647-656.
[14] V. I. Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 25,
1992, 1-82.
[15] V. I. Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming
spaces, IEEE Trans. Infor. Theory 41, 1995, 1303-1321.
[16] V. I. Levenshtein, Universal bounds for codes and designs, Handbook of Coding Theory, V. S. Pless
and W. C. Huffman, Eds., Elsevier, Amsterdam, 1998, Ch. 6, 499-648.
[17] B. Litjens, S. Polak, A. Schrijver, Semidefinite bounds for nonbinary codes based on quadruples,
Designs, Codes and Cryptography, 84, 2016, 87-100.
[18] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-correcting Codes, North-Holland, New York,
1977.
[19] A. Perttula, Bounds for binary and nonbinary codes slightly outside of the Plotkin range, Tampere
University of Technology Publ., 14 (1982).
[20] A. Samorodnitsky, On the optimum of Delsarte’s linear program, J. Combin. Theory, Ser. A 96,
2001, 261-287.
[21] A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming,
IEEE Trans. Inform. Theory 51, 2005, 2859-2866.
[22] V. M. Sidel’nikov, On mutual correlation of sequences, Sov. Math. Dokl. 12(1), (1971), 197-201.
[23] R. J. Stroeker, On integral zeroes of binary Krawtchouk polynomials, Neuw Archive voor Wiskunde,
17(2), 1999, 175-186.
[24] G. Szegő, Orthogonal Polynomials, Amer. Math. Soc. Col. Publ., 23, Providence, RI, 1939.
[25] A. Tietäväinen, Bounds for binary codes just outside the Plotkin range, Inform. Contr. 47, 1980,
85-93.
[26] http://doc.sagemath.org/html/en/reference/coding/sage/coding/code bounds.html.

REFINEMENTS OF LEVENSHTEIN BOUNDS IN q-ARY HAMMING SPACES

17

Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 G Bonchev
Str., 1113 Sofia, Bulgaria, and Faculty of Mathematics and Natural Sciences, SouthWestern University, Blagoevgrad, Bulgaria.
E-mail address: peter@math.bas.bg
Department of Electrical Engineering, Linköping University SE-58183 Linköping, Sweden
E-mail address: danyo.danev@liu.se
Faculty of Mathematics and Informatics, Sofia University, 5 James Bourchier Blvd.,
1164 Sofia, Bulgaria
E-mail address: stoyanova@fmi.uni-sofia.bg

