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₀,…, A_s denote the distance distribution of an (s, N, d)-code C, i.e.,

A_i := |{(x, y) ∈ C²Â  :  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₀^⊥,…, A_s^⊥ of the dual code C^⊥ is always given by the Krawtchouk transformation

A_i^⊥ = A_jK_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₀,…, A_s as well as A₀^⊥,…, 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₀,…, A_s according to the Krawtchouk transformation, i.e., one actually requires that

  A_jK_i(j) ≥ 0

  for i = 0,…, s.

Furthermore, we have

• A₀ = 1 and

• A₁ = … = 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₀ + A₁ + … + 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_jK_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_jK_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_iK_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

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

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₁(X).

• The Bush bounds.

• The Singleton bound with

  p(X) = b^s−k/ = K_i(X).

See also

• Generalization for arbitrary OOAs

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

References

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: 2024-09-05. http://mint.sbg.ac.at/desc_CBoundLP.html