Korobov discovered the component-by-component construction of lattice rules in 1959

Alexey Ustinov recently pointed out that Korobov invented the component-by-component construction of lattice rules in 1959. He provided two references for this result, namely

• @article {MR0104086,
      AUTHOR = {Korobov, N. M.},
       TITLE = {Approximate evaluation of repeated integrals},
     JOURNAL = {Dokl. Akad. Nauk SSSR},
    FJOURNAL = {Doklady Akademii Nauk SSSR},
      VOLUME = {124},
        YEAR = {1959},
       PAGES = {1207–1210},
  }
• Theorem 18 on page 120 in Korobov’s book from 1963:

  @book {MR0157483,
  AUTHOR = {Korobov, N. M.},
  TITLE = {Teoretiko-chislovye metody v priblizhennom analize},
  PUBLISHER = {Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow},
  YEAR = {1963},
  PAGES = {224},
  }

In this post I provide a (rough) translation of the results of Korobov (I do not know Russian, so I only understand the formulae). Indeed, as can be seen below, Korobov used the algorithm which is now called component-by-component construction (and which was re-invented much later by Sloan and Reztsov in Sloan, I. H.; Reztsov, A. V. Component-by-component construction of good lattice rules. Math. Comp. 71 (2002), no. 237, 263–273). He also proved that lattice rules constructed component-by-component achieve the optimal rate of convergence of the integration error for functions in the class (i.e., he showed that where is the number of quadrature points).

Unfortunately many authors were not aware of Korobov’s result, hence Korobov has not received due credit for this result. To rectify this situation somewhat (and help make authors aware of Korobov’s result), we provide the details of Korobov’s result here.

Open internet project 1: Lattice rules for R^s

In this post I describe an approach for constructing lattice rules which might be useful for integration in The aim is to use the main ideas from the construction of digital nets over , see here, and apply them to lattice rules. This is the first project mentioned here.

The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

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.

Exponential Convergence and Tractability of Multivariate Integration for Korobov Spaces

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.