I discuss the recently resubmitted manuscript [DLPW] titled `Exponential Convergence and Tractability of Multivariate Integration for Korobov Spaces‘ by J.D., G. Larcher, F. Pillichshammer, and H. Wo\’zniakowski.
The initial aim of the paper is to show that lattice rules can achieve an exponential rate of convergence for infinitely times differentiable functions. The technical difficulty therein lies in the fact that an application of Jensen’s inequality (which states that for ) yields only a convergence of , where is the number of quadrature points. Though can be arbitrarily large, in the land of asymptotia this is still worse than a convergence of, say, , for some . Hence the first challenge is to find ways to prove convergence rates without relying on Jensen’s inequality.
1. The worst case error in the Korobov space
where , , , and the dual lattice is defined as
This means that for any with we have
2. Averaging argument and Jensen’s inequality
Let us first describe the averaging argument with Jensen’s inequality. This argument works in the following way. Let be such that for all . Then for any we have
where the last inequality follows by using Jensen’s inequality and where is if and otherwise.
The last expression can now be separated into two parts, namely
where is a constant which depends on , , and but not on or .
Thus we obtain
This way we do get with arbitrarily large, but we do not get .
3. Figure of Merit, Trigonometric Degree, and Exponential Rate of Convergence
We now show how we do get an exponential rate of convergence. The main observation is that the sum (1) is dominated by its largest term in the following way.
Let be such that
for all . Then the largest term in (1) is given by (this term may occur several times though). That means that
for all . To shorten the notation let . This leads us to define a so-called figure of merit by
This figure of merit occured elsewhere in the literature already where it is called the trigonometric degree. The motivation for the trigonometric degree is the following. Let with . Then since , and therefore
Hence all nonconstant trigonometric polynomials with degree smaller than get integrted exactly by a lattice rule with generator .
Coming back to our aim of proving an exponential convergence, we show that
Hence the problem of obtaining an exponential rate now comes down to showing a lower bound on . It is known that for each prime number there exists a such that
This now yields an exponential rate of convergence:
4. Further Results
The question arises whether the exponential rate of decay of the worst case error can prevent it from depending on the dimension. That is, is there a constant , independent of and , such that
In the manuscript we show that this is not the case if one wants to have an exponential rate of convergence, see Theorem 3 in [DLPW]. On the other hand if we are satisfied with a convergence of , then we are able to obtain a bound which does not depend on the dimension, see Remark 3 in [DLPW].
In order to obtain tractability one therefore needs to introduce some weights. These weights change the shape of the unit ball of the space we are considering such that certain groups of coordinates are easier to integrate.
The results described above are pure existence results, hence we cannot actually find good generating vectors . We do have, however some constructive results. On is outlined in Section 6 of [DLPW] where we show that the regular grid (as quadrature points) does perform reasonably well, i.e., yields an exponential rate of decay of the worst case error.
Another semi-constructive approach is outlined in Remark 1 in [DLPW] based on algebraic number fields. There it is shown that good generating vector where is the nearest integer to exist. Here form a basis of an algebraic number field of degree . For example, one can choose for . A possible search algorithm is also outlined. The constant in the lower bound for using this method is considerably weaker than for the existence result.
A numerical investigation of this method has shown that one can find reasonably good generating vectors this way. The results are competitive with the result obtained in [CKN]
(though the vectors are not extensible in the dimension as they are in the paper by [CKN]). On the other hand, the study of the trigonometric degree of lattice rules has mainly been aimed at finding the best lattice rule, i.e., at finding such that for given and one has for all . For this aim the outlined construction does not appear to be suitable. In this case exhaustive searches or nearly exhaustive searches are employed.