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 E^\alpha_s (i.e., he showed that P_\alpha = \mathcal{O}(p^{-\alpha} (\ln p)^{\alpha s}) where {}p 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 {}m let

\displaystyle \delta_p(m) = \left\{ \begin{array}{rl} 1 & \mbox{if } p | m, \\ & \\ 0 & \mbox{otherwise.} \end{array} \right.

Further let \overline{m} = \max(1, |m|). Then a classical error criterion for lattice rules is

\displaystyle P_\alpha(a_1,\ldots, a_s) = \sum_{k_1,\ldots, k_s \in \mathbb{Z}} \frac{\delta_p(a_1 k_1 + \cdots + a_s k_s)}{\overline{k_1}^\alpha \cdots \overline{k_s}^\alpha},

where a_1,\ldots, a_s \in \{1,\ldots, p-1\} and \alpha > 1. Another, related criterion is

\displaystyle R(a_1,\ldots, a_s) = \sum_{m_1,\ldots, m_s = -(p-1)}^{p-1} \frac{\delta_p(a_1 m_1 + \cdots + a_s m_s)}{\overline{m_1} \cdots \overline{m_s}}.

The following inequality is useful

\displaystyle \begin{array}{rcl} P_\alpha(a_1,\ldots, a_s) & \le & [R(a_1,\ldots, a_s)]^\alpha \\ && \\ & & + (1+2  \zeta(\alpha) p^{-\alpha})^s-1 \\ && \\ && + \frac{1}{p} (1+2\zeta(\alpha) + 2^\alpha \zeta(\alpha) N^{1-\alpha})^s - \frac{1}{p} (1+2 \zeta(\alpha))^s \\ && \\ & = & [R(a_1,\ldots, a_s)]^\alpha + \mathcal{O}(p^{-\alpha}). \end{array}

Korobov uses a component-by-component approach on a quantity which is related to R(a_1,\ldots, a_s). This quantity is given by

\displaystyle K_s(a_1,\ldots, a_s) = \sum_{k=1}^{p-1} \prod_{j=1}^s [1-2 \ln (2\sin \{\frac{a_j k}{p} \})].

(I renamed it {}K in honour of Korobov, Korobov himself used the letter {}T which is also used below.) The cbc algorithm is carried out using the quantity {}K rather than {}R. Korobov then shows that {}R and \frac{1}{p} K are close (see the Corollary below) and that a component-by-component construction of {}K 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 p \textgreater 1 be an integer. Then

\displaystyle \prod_{k=1}^{p-1} \left(2 \sin \frac{\pi k}{p} \right) = p. >

Proof.

Consider the roots of the polynomial 1-x^p which are given by

\displaystyle x_k = \mathrm{e}^{2\pi \mathrm{i} k/p} \quad \mbox{for } k=0,1,\ldots, p-1.

The polynomial 1-x^p can be factorized

\displaystyle 1-x^p = (1-x) (1+x+\cdots + x^{p-1}).

Hence the roots of 1 + x + \cdots + x^{p-1} are given by x_1, x_2,\ldots, x_{p-1}. Therefore we have

\displaystyle 1 + x + \cdots + x^{p-1} = (x-x_1) \cdots (x-x_{p-1}).

By setting x=1 in the last expression we obtain

\displaystyle p = \prod_{k=1}^{p-1} (1-x_k) = \prod_{k=1}^{p-1} \frac{\mathrm{e}^{\pi \mathrm{i} k/p} - \mathrm{e}^{-\pi \mathrm{i} k/p} }{\mathrm{i}} \left(- \mathrm{i} \mathrm{e}^{\pi \mathrm{i} k/p} \right) = \prod_{k=1}^{p-1} (2 \sin \frac{k\pi}{p}),  > where the last equality follows from

\displaystyle (-\mathrm{i})^{p-1} \prod_{k=1}^{p-1} \mathrm{e}^{\pi \mathrm{i} k/p} = \mathrm{e}^{-\frac{\pi \mathrm{i}}{2} (p-1) + \frac{\pi \mathrm{i}}{p} \frac{p (p-1)}{2}} = 1.

This proves the lemma. \Box

Lemma 2
Let 0 \textless x \textless 1. Then

\displaystyle 1 - 2 \ln (2 \sin \pi x) = \sum_{m=-(p-1)}^{p-1} \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{\overline{m}} + \frac{\theta}{p \min(x,1-x)},

where \overline{m} = \max(1, |m|) and |\theta| \le 1.

Proof.

We use the Fourier series expansion

\displaystyle 1-2 \ln (2\sin \pi x) = 1 + 2 \sum_{m=1}^\infty \frac{\cos 2\pi m x}{m} = \sum_{m=-\infty}^\infty \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{\overline{m}}.

Therefore we have

\displaystyle 1-2\ln (2\sin \pi x) = \sum_{m=-(p-1)}^{p-1} \frac{\mathrm{e}^{2\pi m x}}{\overline{m}} + r,

where

\displaystyle |r| = \left|\sum_{m=p}^\infty \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{m} + \sum_{m=p}^\infty \frac{\mathrm{e}^{-2\pi \mathrm{i} m x}}{m} \right| \le 2 \left|\sum_{m=p}^\infty \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{m} \right|.

We have

\displaystyle \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{m} = \frac{1}{\mathrm{e}^{2 \pi \mathrm{i} x}-1} \left[\frac{\mathrm{e}^{2 \pi \mathrm{i} (m+1) x}}{m+1} - \frac{\mathrm{e}^{2 \pi \mathrm{i} m x}}{m} + \frac{\mathrm{e}^{2 \pi \mathrm{i} (m+1)x }}{m(m+1)} \right].

Thus we have

\displaystyle \left| \sum_{m=p}^\infty \frac{\mathrm{e}^{2\pi \mathrm{i} m x}}{m} \right| = \frac{1}{|\mathrm{e}^{2\pi \mathrm{i} x} -1|} \left|\frac{\mathrm{e}^{2 \pi \mathrm{i} p x} }{p} + \sum_{m=p}^\infty \frac{\mathrm{e}^{2\pi \mathrm{i} (m+1) x}}{m(m+1)} \right| \le  \frac{1}{p \sin \pi x}.

The last inequality follows using the triangular inequality, the estimation |\mathrm{e}^{2\pi \mathrm{i} k x}| = 1, and from

\displaystyle \sum_{m=p}^\infty \frac{1}{m(m+1)} = \sum_{m=p}^\infty \left[\frac{1}{m} - \frac{1}{m+1} \right] = \frac{1}{p}.

Since \sin \pi x \ge 2 \min(x, 1-x) we obtain

\displaystyle |r| \le \frac{2}{p \sin \pi x} \le \frac{1}{p \min(x, 1-x)},

which we can write as

\displaystyle r = \frac{\theta}{p \min(x,1-x)} \quad \mbox{with } |\theta| \le 1.

\Box

Lemma 3
Let u_j, v_j, r_j, u \in \mathbb{R} such that u_j = v_j + r_j, |u_j| \le u and |r_j| \le 1 for j=1,\ldots, s. Then

\displaystyle |u_1\cdots u_s - v_1 \cdots v_s| \le (1+u)^{s-1} (|r_1| + \cdots + |r_s|).

Proof.
For s=1 we have

\displaystyle |u_1-v_1| = |r_1| = (1+u)^0 |r_1|.

Now assume that the result holds for s-1. We have |v_s| = |u_s-r_s| \le u + 1. Then

\displaystyle \begin{array}{rcl} |u_1 \cdots u_s - v_1 \cdots v_s| & = & |(u_1\cdots u_{s-1}- v_1\cdots v_{s-1}) v_s + u_1\cdots u_{s-1} r_s | \\ && \\ & \le & (1+u)^{s-2} (|r_1|+\cdots + |r_{s-1}|) |v_s| + u^{s-1} |r_s| \\ && \\ & \le & (1+u)^{s-1} (|r_1|+\cdots + |r_{s-1}| + |r_s|). \end{array}

\Box

Lemma 4
Let a_1,\ldots, a_s \in \{1,\ldots, p-1\}. We have

\displaystyle \begin{array}{l}  |\sum_{m_1,\ldots, m_s=-(p-1)}^{p-1} \frac{p \delta_p(a_1 m_1 + \cdots + a_s m_s) - 1}{\overline{m_1}\cdots \overline{m_s}} \\ \\ - \sum_{k=1}^{p-1} \prod_{i=1}^s [1-2\ln (2 \sin \pi \left\{\frac{k a_i}{p} \right\} ) ]|  \le s (2+2 \ln p)^s. \end{array}

where

\displaystyle \delta_p(k) = \left\{ \begin{array}{lr} 1 & p | k, \\ & \\ 0 & \mbox{otherwise,} \end{array} \right.

and \overline{m} = \max(1,|m|), and \{x\} = x-\lfloor x \rfloor for nonnegative real numbers {}x.

Lemma 4 implies the following corollary.

Corollary
Let a_1,\ldots, a_s \in \{1,\ldots, p-1\}. We have

\displaystyle \begin{array}{l}  \sum_{m_1,\ldots, m_s=-(p-1)}^{p-1} \frac{\delta_p(a_1 m_1 + \cdots + a_s m_s) }{\overline{m_1}\cdots \overline{m_s}} \\ \\ \le  \frac{1}{p} \sum_{k=1}^{p-1} \prod_{i=1}^s [1-2\ln (2 \sin \pi \left\{\frac{k a_i}{p} \right\} ) ] \\ \\ + \frac{s (2+2 \ln p)^s}{p} + \frac{1}{p} \sum_{m_1,\ldots, m_s = -(p-1)}^{p-1} \frac{1}{\overline{m_1} \cdots \overline{m_s}}. \end{array}

where

\displaystyle \delta_p(k) = \left\{ \begin{array}{lr} 1 & p | k, \\ & \\ 0 & \mbox{otherwise,} \end{array} \right.

and \overline{m} = \max(1,|m|), and \{x\} = x-\lfloor x \rfloor for nonnegative real numbers {}x.

Proof of Lemma 4.
Set

\displaystyle u_j = 1 - 2 \ln (2 \sin \left\{\frac{a_j k}{p} \right\}),

\displaystyle v_j = \sum_{m_j =-(p-1)}^{p-1} \frac{\mathrm{e}^{2\pi \mathrm{i} m_j \frac{a_j k}{p}}}{\overline{m_j}}

and

\displaystyle r_j = \frac{\theta_j}{p \min(\{a_j k/p\}, 1-\{a_j k/p\})},

where |\theta_j| \le 1 and let

\displaystyle u = 1 + 2 \ln p.

Then we have

\displaystyle |u_j| \le 1 + 2|\ln (2 \sin \frac{\pi}{p})| \le 1 + 2\ln p = u.

Further we have

\displaystyle |r_j| \le \frac{|\theta_j|}{p \min(1/p, 1-(p-1)/p)} \le 1.

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

\displaystyle |\sum_{k=1}^{p-1} (u_1\cdots u_s - v_1\cdots v_s) |,

since

\displaystyle \sum_{k=1}^{p-1} \mathrm{e}^{2\pi \mathrm{i} k m/p} = -1 + \sum_{k=0}^{p-1} \mathrm{e}^{2\pi \mathrm{i} k m/p} = p \delta_p(m) - 1.

Using Lemma 3 we obtain therefore

\displaystyle \begin{array}{ll} & |\sum_{k=1}^{p-1} (u_1\cdots u_s - v_1\cdots v_s) |\le  \sum_{k=1}^{p-1} |u_1\cdots u_s - v_1\cdots v_s| \\ & \\ & \le \frac{(2+2\ln p)^{s-1}}{p} \sum_{k=1}^{p-1} \left(\frac{|\theta_1|}{\min(\{a_1 k/p\}, 1-\{a_1k/p\})} + \cdots + \frac{|\theta_s|}{\min(\{a_sk/p\}, 1-\{a_sk/p\})} \right).   \end{array}

Let d=\gcd(p, a_j). Then we have

\displaystyle \begin{array}{rcl}  \sum_{k=1}^{p-1} \frac{1}{\min(\{a_j k/p\}, 1-\{a_j k/p\})} & = & 2 \frac{p}{d} \left(\frac{1}{1/d} + \frac{1}{2/d} + \cdots + \frac{1}{\lfloor d/2\rfloor/d} \right) \\ && \\ & \le & 2p (1 + \frac{1}{2} +\cdots + \frac{1}{\lfloor p/2\rfloor}) \\ && \\ & \le & 2 p (1 + \ln \lfloor p/2 \rfloor) \le 2 p (1+\ln p).\end{array}

Thus we obtain

\displaystyle |\sum_{k=1}^{p-1} (u_1\cdots u_s - v_1\cdots v_s) | \le (2+2\ln p)^s (|\theta_1| + \cdots + |\theta_s|) \le s (2+2\ln p)^s.

\Box

Let E^\alpha_s be the set of functions f:[0,1]^s\to\mathbb{R} given by the Fourier series expansion

\displaystyle f(x_1,\ldots, x_s) = \sum_{k_1,\ldots, k_s = - \infty}^\infty \widehat{f}(k_1,\ldots, k_s) \mathrm{e}^{2\pi \mathrm{i} (k_1 x_1 + \cdots + k_s x_s)},

for which there exists a constant C_f > 0 independent of k_1,\ldots, k_s such that

\displaystyle |\widehat{f}(k_1,\ldots, k_s) | \le \frac{C_f}{\overline{k_1}^\alpha \cdots \overline{k_s}^\alpha} \quad \mbox{for all } k_1,\ldots, k_s \in \mathbb{Z}.

It is known that the integration error for all functions f\in E^\alpha_s with C_f \le 1 is bounded by

\displaystyle \sup_{f \in E^\alpha_s} \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{p} \sum_{n=0}^{p-1} f(\{ n \boldsymbol{a}/p \}) \right| \le  \sum_{k_1,\ldots, k_s \in \mathbb{Z}} \frac{\delta_p(k_1 a_1 + \cdots + k_s a_s)}{\overline{k_1}^\alpha \cdots \overline{k_s}^\alpha},

where \boldsymbol{a}= (a_1,\ldots, a_s).

We can now prove the main result.

Theorem (Korobov, 1959)
Let f \in E_s^\alpha. Let a^\ast_1,\ldots, a^\ast_s \in \{1, 2, \ldots, p-1\} be constructed component by component. That is, set a^\ast_1=1 and for d=2,\ldots, s choose a^\ast_d \in \{1,\ldots, p-1\} which minimizes

\displaystyle T_{d-1}(a_d) = \sum_{k=1}^{p-1} \prod_{j=1}^{d-1} [1-2 \ln (2 \sin \{ka^\ast_j/p\})] [1-2 \ln (2 \sin \{k a_d/p\})].

(Here, a^\ast_1,\ldots, a^\ast_{d-1} are fixed from the previous step.) Then we have

\displaystyle \begin{array}{rcl} \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{p} \sum_{n=0}^{p-1} f(\{n \boldsymbol{a}^\ast/p\}) \right| & = & \mathcal{O}(\frac{(\ln p)^{\alpha s}}{p^\alpha}), \end{array}

where \boldsymbol{a}^\ast = (a^\ast_1,\ldots, a^\ast_s).

Proof.
We show that T_d(a_d^\ast) \le p for d=1,\ldots, s. We consider d=1 first. We have

\displaystyle \sum_{k=1}^{p-1} [1-2\ln (2 \sin \pi k/p)] = p-1  - 2 \ln \prod_{k=1}^{p-1} 2 \sin \pi k/p = p-1 - 2 \ln p,

where we used Lemma 1.

Now let d \textgreater 1 and assume that the result holds for all 1 \le j \textless d. We have

\displaystyle \begin{array}{rcl} T_d(a_d^\ast) & \le & \frac{1}{p-1} \sum_{z=1}^{p-1} T_d(z) \\ && \\ & \le & \sum_{k=1}^{p-1} \prod_{j=1}^{d-1} [1-2\ln (2\sin \{a_j^\ast k/p\})] \frac{1}{p-1} \sum_{z=1}^{p-1} [1-2 \ln (2 \sin \{zk/p\})] \\ && \\ & \le & \frac{p-1-2 \ln p}{p-1} T_{d-1}(a_{d-1}^\ast) \\ && \\ & \le & p. \end{array}

Thus we have T_d(a_d^\ast) \le p for d=1,\ldots, s.

We can now use Lemma 4 to obtain that

\displaystyle \sum_{m_1,\ldots, m_s = -(p-1)}^{p-1} \frac{\delta_p(m_1 a_1^\ast + \cdots + m_s a^\ast_s)-1/p}{\overline{m_1} \cdots \overline{m_s}} \le  \frac{s (2+2\ln p)^s}{p} + 1.

From this we obtain that

\displaystyle  \sum_{m_1,\ldots, m_s = -(p-1)}^{p-1} \frac{\delta_p(m_1 a_1^\ast + \cdots + m_s a^\ast_s)}{\overline{m_1} \cdots \overline{m_s}} \le  \frac{s (2+2\ln p)^s}{p} + 1 + \frac{1}{p} \sum_{m_1,\ldots, m_s=-(p-1)}^{p-1} \frac{1}{\overline{m_1}\cdots \overline{m_s}}.

Since \sum_{m=2}^{p-1} \frac{1}{m} \le \int_1^{p-1} \frac{1}{x} \,\mathrm{d} x \le \ln p, we obtain

\displaystyle  \sum_{m_1,\ldots, m_s = -(p-1)}^{p-1} \frac{\delta_p(m_1 a_1^\ast + \cdots + m_s a^\ast_s)}{\overline{m_1} \cdots \overline{m_s}} \le  \frac{s (2+2\ln p)^s}{p} + 1 + \frac{(3 + 2 \ln p)^s}{p}.

Since the expression on the left-hand side is R(a_1^\ast,\ldots, a_s^\ast) we can use the inequality relating P_\alpha to {}R to obtain the result.
\Box

Advertisements

One response to “Korobov discovered the component-by-component construction of lattice rules in 1959

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s