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.

**1. Some comments**

The proof of Korobov’s result is in Section 2. We first provide some comments on Korobov’s approach.

For integers let

Further let Then a classical error criterion for lattice rules is

where and Another, related criterion is

The following inequality is useful

Korobov uses a component-by-component approach on a quantity which is related to . This quantity is given by

(I renamed it in honour of Korobov, Korobov himself used the letter which is also used below.) The cbc algorithm is carried out using the quantity rather than Korobov then shows that and are close (see the Corollary below) and that a component-by-component construction of yields the optimal order of convergence.

**2. Korobov’s result**

In the following we prove Korobov’s result. Note, the result is entirely from Korobov’s book, it does NOT contain any contribution from the author of this blog. Further, Korobov’s result is actually slightly more general than the one stated here.

To prove the result, we prove several lemmas.

Lemma 1

Let be an integer. Then>

**Proof.**

Consider the roots of the polynomial which are given by

The polynomial can be factorized

Hence the roots of are given by Therefore we have

By setting in the last expression we obtain

> where the last equality follows from

This proves the lemma.

Lemma 2

Let . Thenwhere and

**Proof.**

We use the Fourier series expansion

Therefore we have

where

We have

Thus we have

The last inequality follows using the triangular inequality, the estimation , and from

Since we obtain

which we can write as

Lemma 3

Let such that and for Then

**Proof. **

For we have

Now assume that the result holds for We have Then

Lemma 4

Let We havewhere

and and for nonnegative real numbers

Lemma 4 implies the following corollary.

Corollary

Let We havewhere

and and for nonnegative real numbers

**Proof of Lemma 4. **

Set

and

where and let

Then we have

Further we have

Thus the conditions of Lemma 3 are satisfied. Using the notation just introduced, we can write the left-hand side of the expression in Lemma 4 as

since

Using Lemma 3 we obtain therefore

Let Then we have

Thus we obtain

Let be the set of functions given by the Fourier series expansion

for which there exists a constant independent of such that

It is known that the integration error for all functions with is bounded by

where

We can now prove the main result.

Theorem(Korobov, 1959)

Let Let be constructed component by component. That is, set and for choose which minimizes(Here, are fixed from the previous step.) Then we have

where

**Proof. **

We show that for We consider first. We have

where we used Lemma 1.

Now let and assume that the result holds for all We have

Thus we have for

We can now use Lemma 4 to obtain that

From this we obtain that

Since we obtain

Since the expression on the left-hand side is we can use the inequality relating to to obtain the result.

Thank you for the translation. In an effort to improve the introduction to my joint CTAC paper with Markus Hegland Markus Hegland and Paul Leopardi, “The rate of convergence of sparse grid quadrature on the torus” (submitted), I am going back through the original Russian sources.