In this entry we show how the Walsh degree of a digital net is connected to its t value. This can lead to future research by using ideas developed for finding lattice rules with large trigonometric degree.
Notice that we assume some prior knowledge here, which can be found in the book (Chapters 4 and 10).
where denotes the th row of Then the digital -net property asserts that for all with , the vectors
are linearly independent over If is the smallest value with this property, then the point set is called a strict digital -net. Hence the -value provides information about the number of linearly independent vectors composed of rows from the generating matrices
The logarithmic Walsh degree of exactness
Let have base representation where and For we set Then we define
For vectors we set
Let be a finite set. We define Walsh polynomials (in base ) by
where and the Walsh functions are in base Further we define
We can now define the logarithmic Walsh degree of exactness.
Let be a point set.
Then the logarithmic Walsh degree of exactness is the largest nonnegative integer such that for all finite subsets with we have
(More generally, one can also consider sums of the form in the definition above; but this is not pursued here.)
The logarithmic Walsh degree of exactness of digital nets
Lemma 4.75 in the book (page 182) states the following result.
Let be a prime and let be a digital -net over generated by the matrices over Then for a we have
where for we denote by the -dimensional column vector of -adic digits of , i.e., , and denotes the zero-vector in
Let and for set Then if and only if the row vectors are linearly dependent. Conversely, if are linearly independent, then
Since is a digital -net, it follows that are linearly independent if Therefore we have
From these results it follows that if is a strict digital -net, then
An Ansatz for future research
We have seen that the -value is connected to the logarithmic Walsh degree of exactness. We now give some ideas how this could be used to find constructions of polynomial lattices with small -value.
The idea is to use the analogy between polynomial lattice rules and the logarithmic degree of exactness on the one hand, and lattice rules and the trigonometric degree of exactness on the other hand.
A lattice rule is a quadrature rule given by
where Here denotes the fractional part of a rational number For instance, if then
Let be a finite set. A trigonometric polynomial is a function of the form where and the degree of is the maximum of taken over all The trigonometric degree of exactness is defined analogously as the Walsh degree of exactness with the appropriate changes.
There are several papers which introduce methods to find lattice rules with large trigonometric degree. By the analogy explained above, those methods could also be employed to find polynomial lattices (which are a special class of digital -nets) with small -value (which corresponds to a large logarithmic Walsh degree of exactness). For some ideas used for the construction of lattice rules with small trigonometric degree, see for instance:
- Cools, Ronald; Lyness, James N. Three- and four-dimensional -optimal lattice rules of moderate trigonometric degree. Math. Comp. 70 (2001), no. 236, 1549–1567.
- Lyness, J. N.; Sørevik, Tor Five-dimensional -optimal lattice rules. Math. Comp. 75 (2006), no. 255, 1467–1480.
- Lyness, J. N.; Sørevik, T. Four-dimensional lattice rules generated by skew-circulant matrices. Math. Comp. 73 (2004), no. 245, 279–295.
(This is not a comprehensive list nor is it the most relevant list of papers. Further papers can be found by following the citations in these papers and papers which cite this papers.)
The new ansatz is now to use the ideas for finding lattice rules with large trigonometric degree to find search algorithms for polynomial lattice rules with small -value.