## Gilbert–Varšamov Bound for OOAs

The Gilbert-Varšamov bound for OOAs [1, Theorem 6.1] gives a sufficient condition for finding *s* vectors from **F**_{b}^{m} that can be used for embedding a linear ordered orthogonal array OOA(*b*^{m}, *s*,**F**_{b}, *T *−1, *k*) in a linear OOA(*b*^{m}, *s*,**F**_{b}, *T *, *k*), i.e., for increasing the depth of the original OOA from *T *−1 to *T *. The condition is

*V*

_{b}

^{(T ,s−1)}(

*k*–

*T*) <

*b*

^{m−T+1},

where *V*_{b}^{(T , σ)}(*r*) is the volume of a ball with radius *r* in the NRT-space **F**_{b}^{(T , σ)}.

The proof uses a counting argument, ensuring that for each missing column in the generator matrix the number of vectors that cause prohibited linear dependencies is always strictly less than the number of vectors available in **F**_{b}^{m}. Thus, codes obtained from this method are non-constructive.

A weaker result (corresponding to the Gilbert bound in coding theory) was obtained earlier in [2, Theorem 4]. It states that a linear OOA with parameters as above exists, provided that

*V*

_{b}

^{(T ,s)}(

*k*) <

*b*

^{m+1}.

### Applications

If the condition is satisfied for all depths *T * = *T*_{begin},…, *T*_{end}, an OOA(*b*^{m}, *s*,**F**_{b}, *T*_{end}, *k*) can be obtained from an OOA(*b*^{m}, *s*,**F**_{b}, *T*_{begin} − 1, *k*). The extremal cases for *T*_{begin} and *T*_{end} are particularly important:

For

*T*_{begin}= 1, the existence of the final OOA is established without relying on any previously known OOA.If

*T*_{end}=*k*, an OOA(*b*^{m},*s*,**F**_{b},*k*,*k*) is obtained. The net defined by this OOA is a digital (*m*−*k*,*m*,*s*)-net over**F**_{b}. Thus, for*T*_{end}=*k*the Gilbert-Varšamov bound for OOAs can be used for establishing the existence of a net.

The following combinations for *T*_{begin} and *T*_{end} are noteworthy:

For

*T*_{begin}=*T*_{end}= 1, this method reduces to the well known Gilbert-Varšamov bound from coding theory.For

*T*_{begin}= 1 and*T*_{end}=*k*, the existence of a digital (*m*−*k*,*m*,*s*)-net is shown without relying on any OOA. This is known as the “Gilbert-Varšamov bound for nets” [1, Theorem 6.2].For

*T*_{begin}= 2 and*T*_{end}=*k*, the existence of a digital (*m*−*k*,*m*,*s*)-net is shown based on a linear orthogonal array OA(*b*^{m},*s*,**F**_{b},*k*), i.e., on an OOA with depth 1. Since this OA is the dual of a linear [*s*,*s*−*m*,*k*+ 1]-code, this procedure is known as “embedding a linear code in a net using the Gilbert-Varšamov bound” [1, Theorem 7.1].

### See Also

For

*T*= 1 the normal Gilbert-Varšamov bound for OAs and codes is obtained.This procedure can always be reversed using depth reduction

The case with

*T*_{begin}= 1 and*T*_{end}=*k*is Construction “g” in [1].The case with

*T*_{begin}= 2 and*T*_{end}=*k*is Construction “h” in [1].The cases with

*T*_{begin}= 2,*T*_{end}=*k*, and*k*∈ {3, 4} are listed in [3] as Construction 17 and 20, respectively.

### References

[1] | Jürgen Bierbrauer, Yves Edel, and Wolfgang Ch. Schmid. Coding-theoretic constructions for ( t, m, s)-nets and ordered orthogonal arrays.Journal of Combinatorial Designs, 10(6):403–418, 2002.doi:10.1002/jcd.10015 |

[2] | Michael Yu. Rosenbloom and Michael A. Tsfasman. Codes for the m-metric.Problems of Information Transmission, 33:55–63, 1997. |

[3] | Andrew T. Clayman, Kenneth Mark Lawrence, Gary L. Mullen, Harald Niederreiter, and Neil J. A. Sloane. Updated tables of parameters of ( t, m, s)-nets.Journal of Combinatorial Designs, 7(5):381–393, 1999.doi:10.1002/(SICI)1520-6610(1999)7:5<381::AID-JCD7>3.0.CO;2-S MR1702298 (2000d:05014) |

### 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. “Gilbert–Varšamov Bound for OOAs.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_OGV.html