## 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 Fbm that can be used for embedding a linear ordered orthogonal array OOA(bm, s,Fb, T −1, k) in a linear OOA(bm, s,Fb, T , k), i.e., for increasing the depth of the original OOA from T −1 to T . The condition is

Vb(T ,s−1)(kT ) < bm−T+1,

where Vb(T , σ)(r) is the volume of a ball with radius r in the NRT-space Fb(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 Fbm. 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

Vb(T ,s)(k) < bm+1.

### Applications

If the condition is satisfied for all depths T = Tbegin,…, Tend, an OOA(bm, s,Fb, Tend, k) can be obtained from an OOA(bm, s,Fb, Tbegin − 1, k). The extremal cases for Tbegin and Tend are particularly important:

• For Tbegin = 1, the existence of the final OOA is established without relying on any previously known OOA.

• If Tend = k, an OOA(bm, s,Fb, k, k) is obtained. The net defined by this OOA is a digital (mk, m, s)-net over Fb. Thus, for Tend = k the Gilbert-Varšamov bound for OOAs can be used for establishing the existence of a net.

The following combinations for Tbegin and Tend are noteworthy:

• For Tbegin = Tend = 1, this method reduces to the well known Gilbert-Varšamov bound from coding theory.

• For Tbegin = 1 and Tend = k, the existence of a digital (mk, 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 Tbegin = 2 and Tend = k, the existence of a digital (mk, m, s)-net is shown based on a linear orthogonal array OA(bm, s,Fb, k), i.e., on an OOA with depth 1. Since this OA is the dual of a linear [s, sm, 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].

• 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 Tbegin = 1 and Tend = k is Construction “g” in .

• The case with Tbegin = 2 and Tend = k is Construction “h” in .

• The cases with Tbegin = 2, Tend = k, and k ∈ {3, 4} are listed in  as Construction 17 and 20, respectively.

### References

  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  Michael Yu. Rosenbloom and Michael A. Tsfasman.Codes for the m-metric.Problems of Information Transmission, 33:55–63, 1997.  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)