QuasiRandomDemonstration.nb

Construction

The Construction based on (t,m,s)-Nets and (t,s)-Sequences

-Nets and -Sequences in base

The most successful constructions of low-discrepancy sequences are based on -nets and -sequences. Let and be integers. In the sequel, will typically be a prime or prime power.
A -net in base is point set in consisting of points, such that every -ary box of volume contains points. A -sequence in base is sequence of points in sucht that for all integers and , the point set is a -net in base . The number is the quality parameter. Smaller values of yield more uniform nets and sequences because -ary boxes of smaller volume still contain points.

The Basic Construction Idea

The general construction principle of -nets and -sequences in a base works in a commutative ring with unity and finite order . However, the most efficient construction are based on finite fields of prime or prime power oder. We refer to the monograph of H. Niederreiter.
A one-dimensional sequence is constructed via a suitable transformation of the sequence index which shows that the Niederreiter sequence is just a generalization of the ordinary Van der Corput sequence:

The transformation is obtained from -adic expansion of integers and a linear transformation of the sequence space :

The key of this construction is the specification of the transformation matrix which is obtained from a linear recurring sequence with characteristic polynomial a power of some irreducible polynomial over and suitable initial values. In practice, the sequence is constructed only for indices such that the expansion in base requires number of digits. In this case, it is sufficient to know the transformation matrix on the first dimensions of the sequence space represented as a -dimensional squared matrix over and

For higher dimensional sequences, different pairwise irreducible polynomials are used for every dimension.

Explicit Construction of -Nets and -Sequences - Niederreiter Sequeces

The explicit construction of -sequences work best in finite fields of prime power order . The crucial part is to find suitable field elements . The following result is due to N88, Theorem 1.
Let be a prime power. Select a monic irreducible polynomial with and polynomials which satisfy and . Define via the expansion

where depending on the degree of . For all with , and all define the transformation matrix through . Equation (1) then becomes

Note that for fixed and big enough because for . Moreover, the defining equation (2) implies . For explicit calculation it is therefore sufficient to consider the case .
The -dimensional case is covered by choosing pairwise coprime (monic) polynomials . This defines a -sequence in base with quality parameter .

Linear Recurring Sequences

Expansion as in (3) lead to linear recurring sequences. A sequence of field elements is called a k-th order linear recurring sequence if it satisfies a linear recursion formula

A linear recurring sequence is fully determined by the elements and the number of initial values . The polynomial is called the charactersitic polynomial of the recurring sequence.
To an arbitrary sequence of field elements we associate its generating function .
Given a monic polynomial and a sequence , this sequence is a linear recurring sequence if and only if for some polynomal with . The initial values of the recurring sequence are fully determined by the polynomials and .

The generating polynomial in :

The first 10 elements of the linear recurring sequence with initial values :

The first 10 elements of the impulse response sequence (initial values ):

Selection of

The Case - Impulse Response Sequence

An admissible choice for the polynomials is . In this case equation (4) simplifies to

To calculate for all we use the fact that equation (5) defines a linear recurring sequence. The initial values are obtained by multiplying (6) for with and comparing coefficients. This yields the initial values of the impulse response sequence and . The coefficients for all are determined by the recurrence relation .

The General Case - Linear Recurring Sequences with 'Compatible' Initial Values

The coefficients form a linear recurring sequence with generating function

and characteristic polynomial . The polynomial is fully determined by the initial values and . Hence, the initial values have to be selected to meet the requirements for and stated before equation (7).
In B-F-N it is shown that too many points are close to the origin at the beginning of the sequence (leading zero phenomenon). To alleviate this problem they propose to throw away a few elements at the beginning of the sequence (typically some power of the base ) and to select carefully the initial values of the linear recurring sequence defining the field elements .

Selection of

Linear Polynomials - Faure Sequence

If the dimension satisfies , choose distinct elements . The linear polynomials are pairwise irreducible with degrees . The resulting sequence is a -sequence. If is prime, we obtain the Faure sequence introduced by Faure. The condition is a necessary condition for the existence of a -sequence.

Monic Irreducible Polynomials - Niederreiter Sequence

The minimum value for the quality parameter is obtained by choosing the first monic irreducible polynomials from the list of all monic irreducible polynomials, ordered according to nondecreasing degree. The resulting sequence is a -sequence, where

In particualr, for ever prime power and for ever dimension there exists a -sequence in base . This type of sequence we will call in the sequel Niederreiter sequences.