## Linear Programming Bound

The Linear Programming Bound (LP-bound), established by Delsarte in [1], 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 *A*_{0},…, *A*_{s} denote the distance distribution of an (*s*, *N*, *d*)-code C, i.e.,

*A*

_{i}:= |{(

*x*,

*y*) ∈ C

^{2}:

*d*(

*x*,

*y*) =

*i*}|.

For linear codes the LP-bound can be established using the following result due to MacWilliams [2]: The distance distribution *A*_{0}^{⊥},…, *A*_{s}^{⊥} of the dual code C^{⊥} is always given by the Krawtchouk transformation

*A*

_{i}

^{⊥}=

*A*

_{j}

*K*

_{i}(

*j*)

for 0 ≤ *i* ≤ *s*, where

*K*

_{i}(

*X*) = ( – 1)

^{r}(

*b*– 1)

^{i−r}

are the Krawtchouk polynomials of degree *i* in base *b*, a family of orthogonal polynomials.

Since *A*_{0},…, *A*_{s} as well as *A*_{0}^{⊥},…, *A*_{s}^{⊥} are distance distributions of codes, the following constraints must be satisfied:

*A*_{i}≥ 0 for*i*= 0,…,*s*.*A*_{i}^{⊥}≥ 0 for*i*= 0,…,*s*, where*A*_{i}^{⊥}can be replaced by a linear combination of*A*_{0},…,*A*_{s}according to the Krawtchouk transformation, i.e., one actually requires that*A*_{j}*K*_{i}(*j*) ≥ 0for

*i*= 0,…,*s*.

Furthermore, we have

*A*_{0}= 1 and*A*_{1}= … =*A*_{d−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* = *A*_{0} + *A*_{1} + … + *A*_{s} = 1 + *A*_{d} + … + *A*_{s} 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* = *b*^{s}/*N* of any linear OA(*M*, *s*,**F**_{b}, *d*−1).

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

*A*

_{i}

^{⊥}:=

*A*

_{j}

*K*

_{i}(

*j*)

for *i* = 0,…, *s*. Even though there is (in general) no dual code, it is shown in [1] that the dual distance distribution satisfies *A*_{i}^{⊥} ≥ 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 **F**_{b}.

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

*A*

_{i}:=

*A*

_{j}

^{⊥}

*K*

_{i}(

*j*)

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

*A*

_{i}

^{⊥}=

*A*

_{j}

*K*

_{i}(

*j*)

with *N* := *b*^{s}/*M*. The dual distance of A is defined as the largest integer *d*, such that *A*_{i} = 0 for *i* = 1,…, *d*−1. Based on this notation it is shown in [1] that *A*_{i} ≥ 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* = *b*^{s}/*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 [3].

### 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 +

*c*

_{i}

*K*

_{i}(

*X*)

such that *c*_{i} ≥ 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

*N*≤

*p*(0)

and the number of runs in any OA(*M*, *s*, *S*_{b}, *k*) satisfies

*M*≥

*b*

^{s}/

*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*) =*K*_{i}(*X*).The (dual) Plotkin bound with

*p*(*X*) = = 1 +*K*_{1}(*X*).The Bush bounds.

The Singleton bound with

*p*(*X*) =*b*^{s−k}/ =*K*_{i}(*X*).

### See also

### References

[1] | Philippe Delsarte. An algebraic approach to the association schemes of coding theory. Philips Research Reports Supplement, 10, 1973. |

[2] | F. Jessie MacWilliams. A theorem on the distribution of weights in a systematic code. Bell System Technical Journal, 42:79–94, 1963. |

[3] | Horst Trinker. Linear programming bounds on ordered orthogonal arrays. Master’s thesis, University of Salzburg, Austria, January 2007. |

[4] | A. S. Hedayat, Neil J. A. Sloane, and John Stufken.Orthogonal Arrays.Springer Series in Statistics. Springer-Verlag, 1999. |

[5] | 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) |

### Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.

Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Linear Programming Bound.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CBoundLP.html