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

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.

Lemma

Let be a prime and let be a digital -net over generated by the matrices over Then for a we havewhere 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.