Glossary

(t, m, s)-Net

Let 0 ≤ tm and s ≥ 1 be integers. A (t, m, s)-net in base b is a set of bm points in the s-dimensional half-open unit cube [0, 1)s such that every elementary interval in base b with volume btm contains exactly bt points [1, Definition 2.2]. An elementary interval in base b is an interval of the form

[ai/bki,(ai +1)/bki)

with integers ki ≥ 0 and 0 ≤ ai < bki [1, Definition 2.1].

An (mk, m, s)-net N in base b is equivalent to an OOA (bm, s, Sb,∞, k) (cf. propagation rule extracting embedded OOA). The OOA A is derived from the b-adic expansion of the coordinates of the points of N as follows:

A = {(ηi,j−1(⌊bjxi⌋ modb))(i, j) ∈ {1,…, s}×ℕ  :  xN},

with ηi,j : Sb↔{0,…, b – 1} denoting arbitrary bijections.

A (t, m, s)-net N is called digital over the field Fb if there exist bijections ηi,j : Fb→{0,…, b – 1} such that the corresponding OOA is linear over Fb.

References

 [1] Harald Niederreiter.Point sets and sequences with small discrepancy.Monatshefte für Mathematik, 104(4):273–337, December 1987.doi:10.1007/BF01294651 MR918037 (89c:11120)

(t, s)-Sequence

Let b ≥ 2 and let Sb denote a set with cardinality b. A (t, s)-sequence S in base b is a sequence

x0,x1,… ∈ Sb(s,∞)

such that the OOAs containing the runs xi with jbmi < (j + 1)bm are OOA(bm, s, Sb,∞, mt) for all mt and all j ≥ 0. Thus the point sets defined by these OOAs are (t, m, s)-nets in base b for all mt and all j ≥ 0.

A (t, s)-sequence S is called digital over the finite field Fb if there exists a sequence c1,c2,… ∈ Fb(s,∞) such that c1,…,cm is a basis of the linear OOA {x0,x1,…,xbm−1} for all mt. The ∞×(s,∞)-matrix (c1,c2,…)T is called the generator matrix of S.

The definition given here is equivalent to the one in [1]. The original definition of (t, s)-sequences given in [2, Definition 2.4] defines (t, s)-sequences in terms of the points

()i=1,…, s

in [0, 1]s. Therefore it cannot distinguish between different digit expansions resulting in the same coordinates.

References

 [1] Harald Niederreiter and Chaoping Xing.Low-discrepancy sequences and global function fields with many rational places.Finite Fields and Their Applications, 2(3):241–273, July 1996.doi:10.1006/ffta.1996.0016 MR1398076 (97h:11080) [2] Harald Niederreiter.Point sets and sequences with small discrepancy.Monatshefte für Mathematik, 104(4):273–337, December 1987.doi:10.1007/BF01294651 MR918037 (89c:11120)

Hamming Space

Let S := Sb denote an abelian group with cardinality b. The s-dimensional Hamming space over S is the metric, s-dimensional product space Ss with weight function

w(x) = |{i ∈ {1,…, s}  :  xi ≠ 0}|

and a metric defined as

d (x,y) := w(xy).

In other words, two vectors x,y have distance d = d (x,y) if they differ in exactly d positions.

Usually S is a finite field Fb, which makes Ss = Fbs an s-dimensional vector space.

Hamming space is the ambient space for codes as well as orthogonal arrays.

Ordered Space or NRT-Space

Let S := Sb denote an abelian group with cardinality b. The ordered space or NRT-space of dimension s and depth T over S, denoted by S(s,T ), is the metric, sT -dimensional product space of S with coordinates indexed by the elements of {1,…, s}×{1,…, T }. The metric d : S(s,T )×S(s,T )→ℕ0 is defined as

d (x,y) := w(xy),

where w : S(s,T )→ℕ0 is a weight function defined as

w(x) := max{j ∈ {1,…, T }  :  x(i,j) ≠ 0}.

The depth T can also be unbounded. In this case we write T = ∞, denote the space by S(s,∞), use {1,…, s}×ℕ as the set of coordinates and define w : S(s,∞)→ℕ0∪{∞} by

w(x) := max{j ∈ ℕ  :  x(i,j) ≠ 0}.

NRT-space is the ambient space for NRT-codes as well as ordered orthogonal arrays. For T = 1 NRT-space is equivalent to Hamming space.

In MinT the elements of S(s,T ) are usually written in the form

x = (x(1,1),…, x(1,T) |  ⋯  | x(s,1),…, x(s,T)) = (x(i,1),…, x(i,T))i=1,…, s

or

x = (x(1,1), x(1,2),… |  ⋯  | x(s,1), x(s,2),…) = (x(i,1), x(i,2),…)i=1,…, s

if T = ∞.

Ordered Orthogonal Array

Let M, s, T , and ksT be integers. An ordered orthogonal array OOA(M, s, Sb, T , k) is a multi set of M elements of the NRT-space S(s,T ) such that each possible projection on k coordinates of the form

(1, 1),…,(1, k1) |  ⋯  | (s, 1),…,(s, ks)

with k1 + … + ks = k is balanced, i.e., each of the bk possible k-tuples over S appears the same number of times in such a projection.

An OOA(M, s, Sb, 1, k) is an orthogonal array OA(M, s, Sb, k). Thus OOAs are a generalization of OAs.

An OOA A is linear over the finite field Fb if S = Fb and if A is a linear subspace of Fb(s,T ).

If A is a linear OOA(bm, s,Fb, T , k), its dual C := A is a linear [(s, T ), sT m, k + 1]-NRT-code over Fb and vice versa [1]. Therefore, linear NRT-codes and linear OOAs are equivalent objects and MinT does not distinguish between them.

Every OOA A defines a point set N in [0, 1)s using the mapping

N = {()i=1,…, s  :  xA},

where ηi,j : Sb→{0,…, b – 1} are arbitrary bijections for i = 1,…, s and j = 1,…, T . If T k, N is a (mk, m, s)-net in base b.

References

 [1] Harald Niederreiter and Gottlieb Pirsic.Duality for digital nets and its applications.Acta Arithmetica, 97(2):173–182, 2001.MR1824983 (2001m:11130)

Orthogonal Array

Let M, s, and ks be integers. An orthogonal array OA(M, s, Sb, k) is a multiset of M s-tuples in the Hamming space Ss, with S := Sb denoting a set of cardinality b. An OA has strength k if each possible projection on k coordinates is balanced, i.e., each of the bk possible k-tuples over S appears the same number of times in such a projection.

An orthogonal array A is called linear over the finite field Fb if S = Fb and if A is a linear subspace of Fbs. In this case, the parameters are usually written in the form OA(bm, s,Fb, k) with m denoting the Fb-dimension of A.

If A is a linear OA(bm, s,Fb, k), its dual C := A is a linear [s, sm, k + 1]-code over Fb and vice versa [1]. Therefore, linear codes and linear orthogonal arrays are equivalent objects and MinT does not distinguish between them.

References

 [1] Raj Chandra Bose.On some connections between the design of experiments and information theory.Bulletin de l’Institut International de Statistique, 38(4):257–271, 1961.MR0148190 (26 #5698)

Code

An (s, N, d)-code C over a finite field Fb is a non-empty subset of the s-dimensional Hamming space Fbs with cardinality N such that any two code words of C have Hamming distance at least d, i.e., they differ in at least d positions.

If C is an Fb-linear subspace of Fbs, C is called linear and is denoted as [s, n, d]-code with N = bn, i.e., n is the dimension of C.

If C is a linear [s, n, d]-code over Fb, its dual A := C is a linear orthogonal array OA(bsn, s,Fb, d−1) and vice versa [1]. Therefore, linear codes and linear orthogonal arrays are equivalent objects and MinT does not distinguish between them.

References

 [1] Raj Chandra Bose.On some connections between the design of experiments and information theory.Bulletin de l’Institut International de Statistique, 38(4):257–271, 1961.MR0148190 (26 #5698)

NRT-Code

An ((s, T ), N, d)-NRT-code C over a finite field Fb is a subset of the s-dimensional NRT space Fb(s,T ) with cardinality N such that any two code words of C have NRT-distance at least d. NRT-codes were first studied in detail in [1].

An ((s, 1), N, d)-NRT-code is also an (s, N, d)-code. Thus NRT-codes are a generalization of normal codes.

If C is an Fb-linear subspace of Fb(s,T ), C is called linear and is denoted as [(s, T ), n, d]-code with N = bn, i.e., n is the dimension of C.

If C is a linear [(s, T ), n, d]-code over Fb, its dual A := C is a linear ordered orthogonal array OOA(bsT−n, s,Fb, T , d−1) and vice versa [2]. Therefore, linear NRT-codes and linear OOAs are equivalent objects and MinT does not distinguish between them.

References

 [1] Michael Yu. Rosenbloom and Michael A. Tsfasman.Codes for the m-metric.Problems of Information Transmission, 33:55–63, 1997. [2] Harald Niederreiter and Gottlieb Pirsic.Duality for digital nets and its applications.Acta Arithmetica, 97(2):173–182, 2001.MR1824983 (2001m:11130)

Volume of Ball in Hamming Space

Let Sb denote a set with cardinality b and Sbs the s-dimensional Hamming space over Sb. The spherical shell C(r) in Sbs with center c and radius r ∈ ℕ0 is defined as

C(r) = {xSbs  :  d (x,c) = r}.

The ball B(r) in Sbr with center c and radius r is defined as

B(r) = C(ρ) = {xSbs  :  d (x,c) ≤ r}.

It is easy to see that the volume of C(r) and B(r) is independent of c. It is denoted by vbs(r) and Vbs(r), respectively, and given by the formulas

vbs(r) = (b – 1)r

and

Vbs(r) = vbs(ρ) = (b – 1)ρ.

Volume of Ball in NRT Space

Let Sb denote a set with cardinality b and Sb(s,T ) the s-dimensional NRT-space with depth T . The ball B(r) in Sbs with center c and radius r ∈ ℕ0 is defined as

B(r) = {xSbs  :  d (x,c) ≤ r}.

It is easy to see that the volume of B(r) is independent of c. It is denoted by Vb(s,T )(r) and given by the formula

Vb(s,T )(r) = 1 + (b – 1)hbρh,

with the second sum running over all partitions π of ρ with summands less or equal T , i.e., over all sums π : ρ = 1c1 +2c2 + ⋯ + TcT , where cj ∈ ℕ0 denotes the number of times the summand j appears in π for j = 1,…, T , and h = c1 + ⋯ + cT denotes the total number of summands. A more explicit formula for Vb(s,T ) is

Vb(s,T )(r) = 1 + (b – 1)hbρh( – 1)j.

For T = ∞ the formula simplifies to

Vb(s,∞)(r) = 1 + (b – 1)hbρh

and one has Vb(s,T )(r) = Vb(s,∞)(r) for all rT .

For T = 1 the formula simplifies to Vb(s,1) = Vbs, the volume of a ball in Hamming space.

Constant-Weigth Code

An (s, N, d)-code C over Fb is called a constant-weight code if all code words of C have the same Hamming weight, i.e., w(x) = w for all xC.

Note that a non-trivial linear code can never be a constant weight code, because it contains 0 with w( 0) = 0 as well as a non-zero code word x with w(x) > 0. However, linear codes C exist such that C ∖ { 0} is a constant-weight code.

Projective Code

A linear [s, n, d]-code C over Fb with n ≥ 2 and generator matrix G is called projective, if the s columns of G (interpreted as homogenous coordinates) form distinct points in the projective space PG(n−1, b). This is equivalent to C being a linear orthogonal array with strength at least 2.

Algebraic Function Field

Let Fb denote a finite field. An algebraic function field F with full constant field Fb, denoted by F/Fb is an algebraic extention of the rational function field Fb(x) such that the constant functions in F are exactly the elements of Fb.

Two important parameters of F are the genus, denoted by g(F/Fb), and the number of rational places, denoted by N(F/Fb). For a given field of constants Fb and genus g one is usually interested in finding a field F with g(F/Fb) = g such that N(F/Fb) is maximal. This number is denoted by

Nb(g) := N(F/Fb).

Algebraic function fields F/Fb are in a certain sense equivalent to algebraic curves c over Fb. In this setting, the rational places of F correspond to the rational points of c and the genus of F is the same as the genus of c.

Finite Projective Space

Let u ≥ 1 and b a prime power. Then PG(u, b) denotes the u-dimensional projective space over Fb. The 2-dimensional projective space PG(2, b) is also known as projective plane. PG(u, b) is usually constructed as the set of all one-dimensional subspaces of Fbu+1 and a point x ∈ PG(u, b) is written in homogenous coordinates as

x = (x1 : … : xu+1).

The affine space AG(u, b) can be obtained from PG(u, b) by discarding a hyperplane.

Finite Affine Space

Let u ≥ 1 and b a prime power. Then AG(u, b) denotes the u-dimensional affine space over Fb, usually identified with the vector space Fbu. The 2-dimensional affine space AG(2, b) is also known as affine plane.

AG(u, b) can be embedded in the projective space PG(u, b) using

(x1,…, xu) (x1 : … : xu : 1).

Caps

Caps are sets of points in some space such that no triple of points is collinear, i.e., every line contains at most two points of the cap. A cap containing s points is called an s-cap.

s-caps in the u-dimensional projective space PG(u, b) form the generator matrix of linear orthogonal arrays OA(bu+1, s,Fb, 3) and vice versa. The dual of such an OA is a linear [s, s−(u + 1), 4]-code over Fb. The size of the largest possible cap in PG(u, b) is denoted by m2(u, b).

Arcs

Arcs in a u-dimensional space are sets of points such that every hyperplane contains at most u points of the arc. An arc containing s points is called an s-arc.

s-arcs in the projective space PG(u, b) form a generator matrix of a linear orthogonal array OA(bu+1, s,Fb, u + 1) with index unity and vice versa. The dual of such an OA is a a linear [s, s−(u + 1), u + 2]-MDS-code over Fb.

It follows from the duality of MDS codes that s-arcs in PG(u, b) are equivalent to s-arcs in PG(su, b).

What Makes an Existence Result Constructive?

MinT distinguishes between constructions and pure existence results:

• Existence Results  provide proof of the existence of an object with certain parameters without giving an explicit method for its construction.

• Constructions  are explicit and effective methods for creating the object, i.e., the generator matrices for digital nets, orthogonal arrays, and linear codes, the point sets for nets, and the runs of an orthogonal array.

A method is considered constructive if a computer implementation or at least an algorithm allowing such an implementation is available. If generator matrices are available explicitly (tabulated in print or electronically), the method is also considered constructive.

A brute force search through the finite space of possible generator matrices for given parameters is not considered a constructive method.

Of course, a construction implies an existence result.