MinT - Linear Programming Bound for OOAs

Linear Programming Bound for OOAs

In [1] the linear programming bound for orthogonal arrays is generalized to ordered orthogonal arrays (OOAs).

An Alternative Formulation of the LP Bound for OOAs

An alternative formulation of the LP bound is as follows [2, Section 3]: Fix a depth T , a length/dimension s, and a base b. Let

F = {(f₀,…, f_T) ⊂ ℕ₀^{T +1} : $\displaystyle \sum_{{i=0}}^{{T}}$ f_i = s}

be the set of all types, let the size |⋅| : F→ℕ₀ and breadth $\left\Vert\vphantom{ \cdot}\right.$ ⋅ $\left.\vphantom{ \cdot}\right\Vert$ : F→ℕ₀ of a type be defined by

|(f₀,…, f_T)| := $\displaystyle \sum_{{i=0}}^{{T}}$ if_i

and

$\displaystyle \left\Vert\vphantom{ (f_{0},\ldots,f_{T})}\right.$ (f₀,…, f_T) $\displaystyle \left.\vphantom{ (f_{0},\ldots,f_{T})}\right\Vert$ := $\displaystyle \sum_{{i=1}}^{{T}}$ f_i = s – f₀,

and define 0 := (s, 0,…, 0) ∈ F. Let the multi-variate Krawtchouk polynomial or type (f₀,…, f_T) ∈ F be defined as

K_{(f₀,…, f_T)}(X₀,…, X_T) := b^f-f $\displaystyle \prod_{{i=1}}^{{T}}$ K_{f_i}(X_i−1, X_i + $\displaystyle \sum_{{j=i+1}}^{{T}}$ (X_j – f_j))

where

K_i(X, Y) := $\displaystyle \sum_{{j=0}}^{{i}}$ ( – 1)^j(b – 1)^i−j $\displaystyle \binom{X}{j}$ $\displaystyle \binom{Y}{i-j}$

denotes the normal Krawtchouk polynomial of degree i.

Suppose we can find a polynomial p in T + 1 variables of the form

p(X₀,…, X_T) = $\displaystyle \sum_{{f\in F}}^{}$ c_fP_f(X₀,…, X_T)

such that c_f ≥ 0 for all f ∈ F, c₀ = 1, and p(e) ≤ 0 for all e ∈ F with | e| ≥ k + 1. Then the number of code words in any ((s, T ), N, k + 1)-NRT code satisfies

N ≤ p(0)

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

M ≥ b^Ts/p(0).

Explicit Solutions of the LP Bound for OOAs

Based on the alternative formulation of the LP bound stated above one can derive explicit bounds for OOAs and NRT-codes by finding suitable polynomials p. The following bounds can be derived in this manner:

Generalized Rao bound
Generalized (dual) Plotkin bound, using the optimal linear polynomial
LP bound with quadratic polynomials, using a quadratic polynomial

Bounds Established Using an LP-Solver

By solving the linear program (LP) described above, a lower bound on the number of runs of an OOA with given base b, depth T , strength k, and number of factors s is obtained. Solving such an LP is a computationally involved process, especially if s and T are large, because the number of variables of the LP is given by $\binom{s+T}{T}$ − 1. A second problem is that the LP is numerically unstable, therefore arbitrary precision arithmetic has to be used in order to obtain reliable results.

The first attempt to solving the LP directly was made by Martin and Stinson. In [1] they use Maple with exact arithmetic for solving the LPs for s ≤ 10 for depth T = 2 and for s ≤ 5 for depth T = 4, all for base b = 2 and strength k ≤ 8. This article also contains the solution of an LP for base b = 3 and depth T = 4.

In [3] the computational problems of solving the linear program are discussed. Martin uses CPLEX for obtaining an initial numerical approximation to the solution of the LP, which serves as a starting point for obtaining a feasible solution of the dual LP using exact arithmetic in Maple. Using this method, bounds on the LP bound are obtained for s ≤ 25 for depth T = 2 and for s ≤ 15 for T = 3, all in base b = 2.

For our own calculations (see [4] for details) we use the computer algebra system Mathematica^® with the built-in operation “LinearProgramming”. Currently, MinT contains the following results:

For depth T = 1, see the linear programming bound for OAs
For depth T = 2 we have calculated all LP bounds for s ≤ 25 as well as all bounds for k ≤ 15 and s ≤ 35.
For depth T = 3 we have calculated all LP bounds for s ≤ 11 as well as all bounds for k ≤ 20 and s ≤ 15.
For depth T = 4 we have calculated all LP bounds for s ≤ 8 and k ≤ 19.

References

[1]	William J. Martin and Douglas R. Stinson. Association schemes for ordered orthogonal arrays and (t, m, s)-nets. Canadian Journal of Mathematics, 51(2):326–346, 1999. MR1697147 (2001j:05128)
[2]	Jürgen Bierbrauer. A direct approach to linear programming bounds for codes and tms-nets. Designs, Codes and Cryptography, 42(2):127–143, February 2007. doi:10.1007/s10623-006-9025-6 MR2287187
[3]	William J. Martin. Linear programming bounds for ordered orthogonal arrays and (t, m, s)-nets. In Harald Niederreiter and Jerome Spanier, editors, Monte Carlo and Quasi-Monte Carlo Methods 1998, pages 368–376. Springer-Verlag, 2000.
[4]	Horst Trinker. Linear programming bounds on ordered orthogonal arrays. Master’s thesis, University of Salzburg, Austria, January 2007.

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 for OOAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_OBoundLP.html