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).
Let be an integer and let
be the generating matrices of a digital
-net (see here, page 161, for an introduction to digital
-nets). Here
denotes the finite field of prime order
Let
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
The -value also appears in another context. Let
Let
where
and
denote the Walsh function in base
(see here or my blog entry for background information on Walsh functions (only
is considered there)).
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.
Definition
Letbe 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.
Lemma
Letbe 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
if
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.
I think this looks very interesting. Maybe the concept of a degree of exactness could be used to design point sets which perform well when used for approximation? This would be analogous to Gauss-quadrature rules, which are designed based on degree of exactness for polynomials?
Yes, that’s right, though the basis functions used for approximation are usually not orthogonal. Sparse grids for instance use interpolets – these are functions where the coefficients can be calculated exactly using a few function values. Trigonometric functions and Walsh functions seem not to be suited so well for approximation since the Fourier- and Walsh coefficients themselves need to be approximated first. The papers using this approach fail to get the best possible rate of convergence for dimensions bigger than one.