## Linear Programming Bound

The Linear Programming Bound (LP-bound), established by Delsarte in , is one of the strongest bounds on the number of codewords in a code as well as on the number of runs in an orthogonal array.

Let A0,…, As denote the distance distribution of an (s, N, d)-code C, i.e.,

Ai := |{(x, y) ∈ C2  :  d (x, y) = i}|.

For linear codes the LP-bound can be established using the following result due to MacWilliams : The distance distribution A0,…, As of the dual code C is always given by the Krawtchouk transformation

Ai =  AjKi(j)

for 0 ≤ is, where

Ki(X) = ( – 1)r(b – 1)ir  are the Krawtchouk polynomials of degree i in base b, a family of orthogonal polynomials.

Since A0,…, As as well as A0,…, As are distance distributions of codes, the following constraints must be satisfied:

• Ai ≥ 0 for i = 0,…, s.

• Ai ≥ 0 for i = 0,…, s, where Ai can be replaced by a linear combination of A0,…, As according to the Krawtchouk transformation, i.e., one actually requires that AjKi(j) ≥ 0

for i = 0,…, s.

Furthermore, we have

• A0 = 1 and

• A1 = … = Ad−1 = 0 because C has minimum distance d.

Since any conceivable linear (s, N, d)-code has to satisfy the conditions given above, an upper bound on the number of its code words can be found by maximizing N = A0 + A1 + … + As = 1 + Ad + … + As subject to the stated linear constraints. Thus, solving this linear program yields an upper bound on the number of code words N of any linear (s, N, d)-code, or, equivalently, a lower bound on the number of runs M = bs/N of any linear OA(M, s,Fb, d−1).

For non-linear codes one defines the dual distance distribution by

Ai :=  AjKi(j)

for i = 0,…, s. Even though there is (in general) no dual code, it is shown in  that the dual distance distribution satisfies Ai ≥ 0 for all i = 0,…, s. So the same linear program as discussed above leads to an upper bound on the number of codewords N of an arbitrary (s, N, d)-code over Fb.

In order to establish a lower bound on the number of runs of an arbitrary orthogonal array, an additional result from  is required: Let A denote a (linear or non-linear) OA with M runs and weight distribution Ai for i = 0,…, s. Define Ai as

Ai :=  AjKi(j)

for i = 0,…, s, which can be shown to be equivalent to

Ai =  AjKi(j)

with N := bs/M. The dual distance of A is defined as the largest integer d, such that Ai = 0 for i = 1,…, d−1. Based on this notation it is shown in  that Ai ≥ 0 for all i = 0,…, s and that A is an orthogonal array with strength d−1. Thus, the same linear program as discussed above can be used for obtaining an upper bound on N, which yields a lower bound on M = bs/N.

### Bounds Established Using an LP-Solver

By solving the linear program (LP) described above, a lower bound on the number of runs of an OA with given base b, strength k, and number of factors s is obtained. Solving such an LP is a computationally involved process, especially if s is large, because this number determines the number of variables of the LP. A second problem is that the LP is numerically unstable, therefore arbitrary precision arithmetic has to be used in order to obtain reliable results.

Nevertheless, this LP can be solved if s is not too large. We use the computer algebra system Mathematica® with the built-in operation “LinearProgramming”. Currently, MinT contains all results up to s = 150 and k = 110 for all bases, as well as sporadic results for s up to 300. Most of our calculations have also been verified by using alternative formulations of the LP and by using a different LP-solver. Detailed information about these calculations can be found in .

### An Alternative Formulation of the LP Bound and Explicit Solutions

An alternative formulation of the LP bound is as follows: Suppose we can find a polynomial p of the form

p(X) = 1 + ciKi(X)

such that ci ≥ 0 for i = 1, 2,…, s and p(j) ≤ 0 for j = k + 1, k + 2,…, s. Then the number of code words in any (s, N, k + 1)-code satisfies

Np(0)

and the number of runs in any OA(M, s, Sb, k) satisfies

Mbs/p(0).

Thus, explicit bounds for OAs and codes can be obtained by finding suitable polynomials p and calculating p(0). The following bounds can be derived in this manner:

• The Rao and Hamming bound with

p(X) =    Ki(X).
• The (dual) Plotkin bound with

p(X) = = 1 + K1(X).
• The Bush bounds.

• The Singleton bound with

p(X) = bsk / =   Ki(X).

• Generalization for arbitrary OOAs

• [4, Section 4.5] and [5, Section 18.1]

### References

  Philippe Delsarte.An algebraic approach to the association schemes of coding theory.Philips Research Reports Supplement, 10, 1973.  F. Jessie MacWilliams.A theorem on the distribution of weights in a systematic code.Bell System Technical Journal, 42:79–94, 1963.  Horst Trinker.Linear programming bounds on ordered orthogonal arrays.Master’s thesis, University of Salzburg, Austria, January 2007.  A. S. Hedayat, Neil J. A. Sloane, and John Stufken.Orthogonal Arrays.Springer Series in Statistics. Springer-Verlag, 1999.  Jürgen Bierbrauer.Introduction to Coding Theory.Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004.MR2079734 (2005f:94001)