# 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},
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.

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$