# Glossary

## (*t*, *m*, *s*)-Net

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

*a*

_{i}/

*b*

^{ki},(

*a*

_{i}+1)/

*b*

^{ki})

with integers *k*_{i} ≥ 0 and 0 ≤ *a*_{i} < *b*^{ki} [1, Definition 2.1].

An (*m*−*k*, *m*, *s*)-net N in base *b* is equivalent to an OOA (*b*^{m}, *s*, *S*_{b},∞, *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:

*η*

_{i,j}

^{−1}(⌊

*b*

^{j}

*x*

_{i}⌋ mod

*b*))

_{(i, j) ∈ {1,…, s}×ℕ}:

*∈ N},*

**x**with *η*_{i,j} : *S*_{b}↔{0,…, *b* – 1} denoting arbitrary bijections.

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

### 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 *S*_{b} denote a set with cardinality *b*. A (*t*, *s*)-sequence S in base *b* is a sequence

**x**_{0},

**x**_{1},… ∈

*S*

_{b}

^{(s,∞)}

such that the OOAs containing the runs **x**_{i} with *jb*^{m} ≤ *i* < (*j* + 1)*b*^{m} are OOA(*b*^{m}, *s*, *S*_{b},∞, *m*−*t*) for all *m* ≥ *t* and all *j* ≥ 0. Thus the point sets defined by these OOAs are (*t*, *m*, *s*)-nets in base *b* for all *m* ≥ *t* and all *j* ≥ 0.

A (*t*, *s*)-sequence S is called digital over the finite field **F**_{b} if there exists a sequence **c**_{1},**c**_{2},… ∈ **F**_{b}^{(s,∞)} such that **c**_{1},…,**c**_{m} is a basis of the linear OOA {**x**_{0},**x**_{1},…,**x**_{bm−1}} for all *m* ≥ *t*. The ∞×(*s*,∞)-matrix (**c**_{1},**c**_{2},…)^{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* := *S*_{b} denote an abelian group with cardinality *b*. The *s*-dimensional Hamming space over *S* is the metric, *s*-dimensional product space *S*^{s} with weight function

*w*(

*) = |{*

**x***i*∈ {1,…,

*s*} :

*x*

_{i}≠ 0}|

and a metric defined as

*d*(

*,*

**x***) :=*

**y***w*(

*–*

**x***).*

**y**In other words, two vectors * x*,

*have distance*

**y***d*=

*d*(

*,*

**x***) if they differ in exactly*

**y***d*positions.

Usually *S* is a finite field **F**_{b}, which makes *S*^{s} = **F**_{b}^{s} 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* := *S*_{b} 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*(

*–*

**x***),*

**y**where *w* : *S*^{(s,T )}→ℕ_{0} is a weight function defined as

*w*(

*) := max{*

**x***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*(

*) := max{*

**x***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 *k* ≤ *sT * be integers. An ordered orthogonal array OOA(*M*, *s*, *S*_{b}, *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

*k*

_{1}) | ⋯ | (

*s*, 1),…,(

*s*,

*k*

_{s})

with *k*_{1} + … + *k*_{s} = *k* is balanced, i.e., each of the *b*^{k} possible *k*-tuples over *S* appears the same number of times in such a projection.

An OOA(*M*, *s*, *S*_{b}, 1, *k*) is an orthogonal array OA(*M*, *s*, *S*_{b}, *k*). Thus OOAs are a generalization of OAs.

An OOA A is linear over the finite field **F**_{b} if *S* = **F**_{b} and if A is a linear subspace of **F**_{b}^{(s,T )}.

If A is a linear OOA(*b*^{m}, *s*,**F**_{b}, *T *, *k*), its dual C := A^{⊥} is a linear [(*s*, *T *), *sT *−*m*, *k* + 1]-NRT-code over **F**_{b} 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

_{i=1,…, s}:

*∈ A},*

**x**where *η*_{i,j} : *S*_{b}→{0,…, *b* – 1} are arbitrary bijections for *i* = 1,…, *s* and *j* = 1,…, *T *. If *T * ≥ *k*, N is a (*m*−*k*, *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 *k* ≤ *s* be integers. An orthogonal array OA(*M*, *s*, *S*_{b}, *k*) is a multiset of *M* *s*-tuples in the Hamming space *S*^{s}, with *S* := *S*_{b} 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 *b*^{k} 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 **F**_{b} if *S* = **F**_{b} and if A is a linear subspace of **F**_{b}^{s}. In this case, the parameters are usually written in the form OA(*b*^{m}, *s*,**F**_{b}, *k*) with *m* denoting the **F**_{b}-dimension of A.

If A is a linear OA(*b*^{m}, *s*,**F**_{b}, *k*), its dual C := A^{⊥} is a linear [*s*, *s*−*m*, *k* + 1]-code over **F**_{b} 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 **F**_{b} is a non-empty subset of the *s*-dimensional Hamming space **F**_{b}^{s} 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 **F**_{b}-linear subspace of **F**_{b}^{s}, C is called linear and is denoted as [*s*, *n*, *d*]-code with *N* = *b*^{n}, i.e., *n* is the dimension of C.

If C is a linear [*s*, *n*, *d*]-code over **F**_{b}, its dual A := C^{⊥} is a linear orthogonal array OA(*b*^{s−n}, *s*,**F**_{b}, *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 **F**_{b} is a subset of the *s*-dimensional NRT space **F**_{b}^{(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 **F**_{b}-linear subspace of **F**_{b}^{(s,T )}, C is called linear and is denoted as [(*s*, *T *), *n*, *d*]-code with *N* = *b*^{n}, i.e., *n* is the dimension of C.

If C is a linear [(*s*, *T *), *n*, *d*]-code over **F**_{b}, its dual A := C^{⊥} is a linear ordered orthogonal array OOA(*b*^{sT−n}, *s*,**F**_{b}, *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 *S*_{b} denote a set with cardinality *b* and *S*_{b}^{s} the *s*-dimensional Hamming space over *S*_{b}. The spherical shell *C*(*r*) in *S*_{b}^{s} with center * c* and radius

*r*∈ ℕ

_{0}is defined as

*C*(

*r*) = {

*∈*

**x***S*

_{b}

^{s}:

*d*(

*,*

**x***) =*

**c***r*}.

The ball *B*(*r*) in *S*_{b}^{r} with center * c* and radius

*r*is defined as

*B*(

*r*) =

*C*(

*ρ*) = {

*∈*

**x***S*

_{b}

^{s}:

*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

*v*

_{b}

^{s}(

*r*) and

*V*

_{b}

^{s}(

*r*), respectively, and given by the formulas

*v*

_{b}

^{s}(

*r*) = (

*b*– 1)

^{r}

and

*V*

_{b}

^{s}(

*r*) =

*v*

_{b}

^{s}(

*ρ*) = (

*b*– 1)

^{ρ}.

## Volume of Ball in NRT Space

Let *S*_{b} denote a set with cardinality *b* and *S*_{b}^{(s,T )} the *s*-dimensional NRT-space with depth *T *. The ball *B*(*r*) in *S*_{b}^{s} with center * c* and radius

*r*∈ ℕ

_{0}is defined as

*B*(

*r*) = {

*∈*

**x***S*

_{b}

^{s}:

*d*(

*,*

**x***) ≤*

**c***r*}.

It is easy to see that the volume of *B*(*r*) is independent of * c*. It is denoted by

*V*

_{b}

^{(s,T )}(

*r*) and given by the formula

*V*

_{b}

^{(s,T )}(

*r*) = 1 + (

*b*– 1)

^{h}

*b*

^{ρ−h},

with the second sum running over all partitions *π* of *ρ* with summands less or equal *T *, i.e., over all sums *π* : *ρ* = 1*c*_{1} +2*c*_{2} + ⋯ + *Tc*_{T }, where *c*_{j} ∈ ℕ_{0} denotes the number of times the summand *j* appears in *π* for *j* = 1,…, *T *, and *h* = *c*_{1} + ⋯ + *c*_{T } denotes the total number of summands. A more explicit formula for *V*_{b}^{(s,T )} is

*V*

_{b}

^{(s,T )}(

*r*) = 1 + (

*b*– 1)

^{h}

*b*

^{ρ−h}( – 1)

^{j}.

For *T * = ∞ the formula simplifies to

*V*

_{b}

^{(s,∞)}(

*r*) = 1 + (

*b*– 1)

^{h}

*b*

^{ρ−h}

and one has *V*_{b}^{(s,T )}(*r*) = *V*_{b}^{(s,∞)}(*r*) for all *r* ≤ *T *.

For *T * = 1 the formula simplifies to *V*_{b}^{(s,1)} = *V*_{b}^{s}, the volume of a ball in Hamming space.

## Constant-Weigth Code

An (*s*, *N*, *d*)-code C over **F**_{b} is called a constant-weight code if all code words of C have the same Hamming weight, i.e., *w*(* x*) =

*w*for all

*∈ C.*

**x**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*(

*) > 0. However, linear codes C exist such that C ∖ { 0} is a constant-weight code.*

**x**## Projective Code

A linear [*s*, *n*, *d*]-code C over **F**_{b} with *n* ≥ 2 and generator matrix * G* is called projective, if the

*s*columns of

*(interpreted as homogenous coordinates) form distinct points in the projective space PG(*

**G***n*−1,

*b*). This is equivalent to C being a linear orthogonal array with strength at least 2.

## Algebraic Function Field

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

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

*N*

_{b}(

*g*) :=

*N*(

*F*/

**F**

_{b}).

Algebraic function fields *F*/**F**_{b} are in a certain sense equivalent to algebraic curves *c* over **F**_{b}. 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 **F**_{b}. 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 **F**_{b}^{u+1} and a point * x* ∈ PG(

*u*,

*b*) is written in homogenous coordinates as

*= (*

**x***x*

_{1}: … :

*x*

_{u+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 **F**_{b}, usually identified with the vector space **F**_{b}^{u}. 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

*x*

_{1},…,

*x*

_{u}) (

*x*

_{1}: … :

*x*

_{u}: 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(*b*^{u+1}, *s*,**F**_{b}, 3) and vice versa. The dual of such an OA is a linear [*s*, *s*−(*u* + 1), 4]-code over **F**_{b}. The size of the largest possible cap in PG(*u*, *b*) is denoted by *m*_{2}(*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(*b*^{u+1}, *s*,**F**_{b}, *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 **F**_{b}.

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

### See Also

Arc at

## 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.

## 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. “Glossary.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/glossary.php