## Varšamov–Edel Lengthening

In [1, Theorem 1.23] an improvement on the Varšamov bound is given.

Let H be the generator matrix of a linear orthogonal array OA(bm, s,Fb, k). Let ρκ(H) denote the number of vectors in Fbm that can be obtained by a linear combination of κ or less columns of H. If ρk−1(H) < bm, a vector xFbm can be found that is linearly independent of any k−1 columns in H. Thus (H|x) is the generator matrix of a linear OA(bm, s + 1,Fb, k).

Now the original Varšamov bound follows from

ρk−1(H) ≤ Vbs(k−1),

where Vbs(r) denotes the volume of a ball with radius r in the Hamming space Fbs.

Better OAs can be obtained by constructing a sequence of OAs (Ai)i ≥ 0 with parameters OA(bmi, si,Fb, k) and generator matrices Hi as follows: One starts with an existing OA A0 and estimates

ρκ(H0) ≤ N0(κ) := minbmVbs(κ)

for κ = 0,…, k−1. Note that ρ0(Hi) = Ni(0) = 1 for all i. Then one constructs Ai+1 from Ai using one of the following two methods:

• If Ni(k – 1) < bmi, a vector xFbmi exists such that Hi+1 := (Hi|x) is the generator matrix of an OA(bmi, si +1,Fb, k) which we use as Ai+1. Furthermore we have

ρκ(Hi+1) ≤ Ni+1(κ) := min{bmi+1Ni(κ) + (b – 1)Ni(κ – 1)}

for 1,…, k−1.

• If Ni(k – 1) = bmi, we construct an OA Aiʹ with generator matrix

Hiʹ := ,

where r ≥ 1 is chosen as small as possible such that

ρk−1(Hiʹ) ≤ Niʹ(k – 1) := (b – 1)jNi(k – 1 – j) < bmi+r,

which can be shown to be equivalent to determining the smallest r such that Ni(k – 1 – r) < bmi. Now a vector xFbmi+r can be found such that Hi+1 := (Hiʹ|x) is the generator matrix of an OA(bmi+r, si + r + 1,Fb, k) used for Ai+1. The Ni+1 can be calculated based on Ni using the formula

ρκ(Hi+1) ≤ Ni+1(κ) := minbmi+1(b – 1)jNi(κj).