Proceedings of the Steklov Institute of Mathematics, Vol. 218, 1997, pp. 72–93. Translated from Trudy Matematicheskogo Instituta imeni V. A. Steklova, Vol. 218, 1997, pp. 77–98. Original Russian Text Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997 by Voronin. English Translation Copyright \begin{matrix}c \\ ◯ \end{matrix} by ���� �����/Interperiodica Publishing (Russia).

On Interpolation Formulas

S. M. Voronin

Received February, 1997

NOTATION

Suppose that ℕ, ℤ, ℚ, ℝ, and ℂ denote the set of natural numbers, the set of integers, the set of rational numbers, the set of real numbers, and the set of complex numbers, respectively, K is a finite algebraic extension of the field ℚ, ℤ_{K} is the set of integers of the field K, ω_{1}, ω_{2}, …, ω_{m} is a certain fundamental basis of the field K, N(α) is the norm of the number α ∈ K with respect to ℚ, ℙ is the set of prime numbers, p, p_{1}, …, p_{k} are prime numbers, 𝔻_{K} is the semigroup of integer divisors of the field K. Suppose that for 𝔞 ∈ 𝔻_{K} N(𝔞) denotes the norm of the divisor of 𝔞 with respect to ℚ; ℙ_{K} is the set of prime divisors of the field K; 𝔭, 𝔭_{1}, 𝔭_{2}, … are prime divisors of the field K; for a finite set M, the notation |M| denotes the number of elements belonging to M; if x and y belong to ℝ^{m}, then ⟨x, y⟩ denotes the inner product of x and y; for the Fourier polynomial

f(x) = ∑_{n∈ℤ^{m}} c_{x}e^{2πi⟨n,x⟩}, x ∈ ℝ^{m},

we set

Spec f = {n : n ∈ ℤ^{m}, c_{n} ≠ 0};

for M ∈ ℤ^{m}, |M| < ∞, we set

L_{M} = {f(x) : f(x) = ∑_{n∈ℤ^{m}} c_{n}e^{2πi⟨n,x⟩}, Spec f ⊂ M};

if M ⊂ ℤ^{m}, |M| < ∞, then

D_{M}(x) = D(x, M) = ∑_{n∈M} e^{2πi⟨n,x⟩};

for 𝔭 ∈ ℙ_{K}, α ∈ ℤ_{K} \ {0}, the function ord_{𝔭} α is defined by the relation

(α) = ∏_{𝔭∈ℙ_{K}} 𝔭^{ord_{𝔭} α},

where (α) denotes the principal divisor corresponding to α; for α ∈ ℤ_{K}, 𝔭 ∈ ℙ_{K}, the function δ(α, 𝔭) is defined by the relation

δ(α, 𝔭) = δ_{𝔭}(α) = \{ \begin{matrix}1 & if 𝔭 is a divisor of α \\ 0 & otherwise; \end{matrix}

for α, β ∈ ℤ_{K}, 𝔭 ∈ ℙ_{K},

χ(α; 𝔭, β) = δ_{𝔭}(α − β);

for n = (n_{1}, n_{2}, …, n_{m}), we set

ñ = n_{1}ω_{1} + n_{2}ω_{2} + ⋯ + n_{m}ω_{m};

for α ∈ ℤ_{K}, we set \overline{α} = (n_{1}, …, n_{m}), where n_{j} are defined by the relation α = n_{1}ω_{1} + ⋯ + n_{m}ω_{m}; for α ∈ ℤ_{K} and M ⊂ ℤ^{m} the notation α ∈ M (mod 𝔭) means that there exists a vector n ∈ M for which the relation

α ≡ ñ (mod 𝔭)

holds; in particular, for h ∈ ℤ, M ⊂ ℤ, the notation h ∈ M (mod p) means that there exists n ∈ M for which h ≡ n (mod p); ≪ is Vinogradov’s symbol.

1. FORMULATION OF THE RESULTS

In this paper, we present a method for constructing interpolation formulas for Fourier polynomials with a given spectrum. This method is based on the application of division theory in the ring ℤ as well as in the rings of integers in finite algebraic extensions of the field ℚ. The number of interpolation nodes coincides with the total number of harmonics of the Fourier polynomial with an accuracy up to the degree of the logarithm of the maximal norm of the harmonic entering into the spectrum of this polynomial.

This method allows one to compute effectively the interpolation nodes.

The proofs of theorems are based on Lemmas 3.1 and 3.2, which are of combinatorial character and are close in spirit to the large sieve. The choice of L in Theorems 1.1 and 1.3 is explained by the wish to diminish the number of terms in interpolation formulas. If we choose L = 2, then the obtained interpolation formulas become less cumbersome but contain more terms.

It should be noted that the idea of “thinning out” the spectrum of the Fourier polynomial with the subsequent construction of interpolation formulas for polynomials with a spaced out spectrum belongs to K. K. Frolov. The author is very grateful to him.

Theorem 1.1. Let M_{0} ⊂ ℤ, and let

N = max_{n∈M_{0}} |n|, Q_{0} = max(1000, 2|M_{0}| ln(2N + 20)).

Then

(a) there exists k ≪ \frac{ln(|M_{0}| + 20)}{ln ln(|M_{0}| + 20)},

(b) for every j = 1, 2, …, k, there exist numbers p_{j} ∈ ℙ, p_{j} ∈ (Q_{0}, 2Q_{0}], and sets M_{j} ⊂ M_{0} such that

M_{j} ⊂ M_{0} \ ⋃_{l=1}^{j−1} M_{l},  ⋃_{j=1}^{k} M_{j} = M_{0},  (1)

(c) for every j ∈ [1, k], j ∈ ℕ, there exist numbers q_{j}^{(h)}, h = 1, 2, …, p_{j}, such that
q_{j}^{(h)} ∈ ℙ, q_{j}^{(h)} < max(1000, 2 ln^{2}(|M_{0}| + 20) ln(2N + 3));

(d) for every Fourier polynomial f_{0} ∈ L_{M_{0}}, the relation

f_{0}(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} \frac{1}{p_{j_{1}}} ∑_{\begin{matrix}h=1 \\ h∈M_{j_{1}} (mod p_{j_{1}}) \end{matrix}}^{p_{j_{1}}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{p_{j_{1}}} exp(−2πi\frac{hν}{p_{j_{1}}} )
× ∑_{κ=1}^{q_{1}^{(κ)}}f_{0}(\frac{κ}{q_{j_{1}}^{(h)}} + \frac{ν}{p_{j_{1}}} )(P_{j_{l}} ⋯ P_{j_{2}}D_{M_{j_{1}},h}(∗ − \frac{κ}{q_{j_{1}}^{(h)}} )(x)),  (2)

holds, where the linear operators P_{j} are defined by the formula

(P_{j}φ)(x) = \frac{1}{p_{j}} ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod p_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} exp(−2πi\frac{hν}{p_{j}} ) ∑_{κ=1}^{q_{j}^{(h)}}φ(\frac{ν}{p_{j}} + \frac{h}{q_{j}^{(h)}} )D_{M_{j},h}(x − \frac{κ}{q_{j}^{(h)}} ),

M_{j,h} = {n : n ∈ M_{j}, n ≡ h (mod p_{j})}.

Remark. The total number of interpolation nodes in formula (2) does not exceed

≪ |M| ln^{4}(|M_{0}| + 20) ln^{2}(2N + 3).

Theorem 1.2. Let the whole notation and all the conditions of Theorem 1.1 be preserved. Then we have the relation

f_{0}(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} \frac{1}{p_{j_{1}}} ∑_{\begin{matrix}h=1 \\ h∈M_{j_{1}} (mod p_{j_{1}}) \end{matrix}}^{p_{j_{1}}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{p_{j_{1}}} exp(−2πi\frac{hν}{p_{j_{1}}} )

× ∑_{κ=1}^{q_{1}^{(κ)}}f_{0}(\frac{κ}{q_{j_{1}}^{(h)}} + \frac{ν}{p_{j_{1}}} ) ∑_{n_{1}∈M_{j_{1},h}} exp(−2πin_{1} \frac{κ}{q_{j_{1}}^{(h)}} )A(x),

where

A(x) = ∑_{\begin{matrix}h_{2}=1 \\ h_{2}∈M_{j_{2}} (mod p_{j_{2}}) \end{matrix}}^{p_{j_{2}}} ∑_{n_{2}∈M_{j_{2},h_{2}}} ⋯ ∑_{\begin{matrix}h_{l}=1 \\ h_{l}∈M_{j_{l}} (mod p_{j_{l}}) \end{matrix}}^{p_{j_{l}}} ∑_{n_{l}∈M_{j_{l},h_{l}}} χ(h_{2}; p_{2}, n_{1})χ(n_{1}; q_{j_{2}}^{(h_{1})}, n_{2})
× χ(h_{3}; p_{j_{3}}, n_{2})χ(n_{2}; q_{j_{3}}^{(h_{3})}, n_{3}) ⋯ χ(h_{l}; p_{l}, n_{l−1})χ(n_{l−1}; q_{j_{l}}^{(h_{l})}, n_{l}) exp(2πin_{l}x).

Theorem 1.3. Let M_{0} ⊂ ℤ^{m}, K be the field of algebraic numbers, [K : ℚ] = m, and let

N = max_{(n_{1},...,n_{m})∈M_{0}} max_{1≤j≤m} |n_{j}|.

Then there exist positive constants c_{0} and c_{1} which depend only on K and are such that for Q_{0} ≥ max(c_{1}, 4m|M_{0}| ln(c_{0}N)) the following conditions hold:

(a) there exists k ∈ ℕ, k ≪ \frac{ln(|M_{0}| + 20)}{ln ln(|M_{0}| + 20)},

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

(b) for every j = 1, …, k there exist prime divisors 𝔭_{j}, N(𝔭_{j}) = p_{j} ∈ ℙ, p_{j} ∈ (Q_{0}, 2Q_{0}], and sets M_{j} for which (1) holds,

(c) for every j ∈ [1, k], j ∈ ℕ, there exist a vector a_{j} ∈ ℤ^{m}, prime numbers q_{j}^{(h)}, h = 1, 2, …, p_{j},

q_{j}^{(h)} < max(c_{1}, m ln^{2}(|M_{0}| + 20) ln(N + 20)),

and vectors a_{j}^{(h)} ∈ ℤ^{m} such that for every Fourier polynomial f_{0} ∈ L_{M_{0}} the relation

f_{0}(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} ∑_{\begin{matrix}h=1 \\ h∈M_{j_{1}} (mod 𝔭_{j_{1}}) \end{matrix}}^{p_{j_{1}}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{q_{j_{1}}} \frac{1}{p_{j_{1}}} ∑_{ν_{1}modp_{j_{1}}} exp(−2πi⟨\overline{h}, a_{j_{1}}⟩\frac{ν}{p_{j_{1}}} )

× f_{0}(\frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{1}}{p_{j_{1}}} a_{j})(P_{j_{l}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)})(x)),

holds, where the operators P_{j} are defined by the formula

(P_{j}φ)(x) = ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν}{p_{j}} )φ(\frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{j}}{p_{j}} a_{j}))

× D_{M_{j},h}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}), M_{j,h} = \{n : n ∈ M_{j}, ⟨a_{j}, n⟩ ≡ ⟨a_{j}, \overline{h}⟩ (mod p_{j})\}.

Theorem 1.4. In the notation of Theorem 1.3 and under its conditions the following formula holds true:

f_{0}(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} ∑_{\begin{matrix}h=1 \\ h∈M_{j_{1}} (mod 𝔭_{j_{1}}) \end{matrix}}^{p_{j_{1}}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{q_{j_{1}}} \frac{1}{p_{j_{1}}} ∑_{ν_{1}modp_{j_{1}}} exp(−2πi⟨\overline{h}, a_{j_{1}}⟩\frac{ν}{p_{j_{1}}} )

× f_{0}(\frac{ν}{q_{j_{1}}^{(h)}} a_{j}^{(h)} + \frac{ν_{1}}{p_{j_{1}}} a_{j})(  ∑_{\begin{matrix}h_{2}=1 \\ h_{2}∈M_{j_{2}} (mod 𝔭_{j_{2}}) \end{matrix}}^{p_{j_{2}}} ∑_{n_{2}∈M_{j_{2},h_{2}}} ⋯ ∑_{\begin{matrix}h_{l}=1 \\ h_{l}∈M_{j_{l}} (mod 𝔭_{j_{l}}) \end{matrix}}^{p_{j_{l}}}

× ∑_{n_{l}∈M_{j_{l},h_{l}}} δ_{p_{j_{2}}} (⟨n − \overline{h}_{2}, a_{j_{2}}⟩)δ_{q_{j_{2}}^{(h_{2})}}(⟨n − n_{2}, a_{j_{2}}^{(h_{2})}⟩) ⋯

× δ_{p_{j_{l}}} (⟨n_{l−1} − \overline{h}_{l}, a_{j_{l}}⟩)δ_{q_{j_{l}}^{(h_{l})}}(⟨n_{l−1} − n_{l}, a_{j_{l}}^{(h_{l})}⟩) exp(2πi⟨n_{l}, x⟩)).

2. AUXILIARY LEMMAS

Lemma 2.1. Let

f(x) = ∑_{n∈M} c_{n}e^{2πinx}, M ⊂ ℤ, |M| < ∞, x ∈ ℝ.

Let q ∈ ℙ be such that for every n ∈ M \ {0} we have q ∤ n. Then

∫_{0}^{1} f(x) dx = \frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} ).

Proof. We have the chain of equalities

\frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} ) = \frac{1}{q} ∑_{ν=0}^{q−1} ∑_{n∈M} c_{n}e^{2πinν/q} = ∑_{n∈M} c_{n} \frac{1}{q} ∑_{ν=0}^{q−1} e^{2πinν/q} = c_{0} = ∫_{0}^{1} f(x) dx.

This proves the lemma.

Lemma 2.2. Let

f(x) = ∑_{n∈M} c_{n}e^{2πinx},  |M| < ∞.  (3)

Assume that q ∈ ℙ and

q ∤ M = ∏_{\begin{matrix}n_{1},n_{2}∈M \\ n_{1}≠n_{2} \end{matrix}} |n_{1} − n_{2}|.

Then the relation

f(x) = \frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} )D_{M}(x − \frac{ν}{q} )

holds.

Proof. By the conditions of the lemma, it follows from Lemma 2.1 that

c_{n} = ∫_{0}^{1} f(x)e^{−2πinx} dx = \frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} )e^{−2πinν/q}

for each n ∈ M. Therefore

f(x) = ∑_{n∈M} c_{n}e^{2πinx} = ∑_{n∈M}(\frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} )e^{−2πinν/q})e^{2πinx}

= \frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} ) ∑_{n∈M} e^{2πin(x−ν/q)} = \frac{1}{q} ∑_{ν=0}^{q−1} f(\frac{ν}{q} )D_{M}(x − \frac{ν}{q} ).

The lemma is proved.

Lemma 2.3. Let M ⊂ ℤ, p ∈ ℙ, and h ∈ ℕ. Let

f_{p,h}(x) = ∑_{\begin{matrix}n∈M \\ n≡h (mod p) \end{matrix}} c_{n}e^{2πinx}

for f(x) satisfying (3). Then the relation

f_{p,h}(x) = \frac{1}{p} ∑_{ν=1}^{p} e^{−2πihν/p}f(x + \frac{ν}{p} )

holds.

Proof. We have the chain of equalities

\frac{1}{p} ∑_{ν=1}^{p} e^{−2πihν/p}f(x + \frac{ν}{p} ) = \frac{1}{p} ∑_{ν=0}^{p−1} e^{−2πihν/p} ∑_{n∈M} c_{n}e^{2πin(x+ν/p)}

= ∑_{n∈M} c_{n}e^{2πinx}(\frac{1}{p} ∑_{ν=0}^{p−1} exp(2πi\frac{n − h}{p}ν)) = ∑_{\begin{matrix}n∈M \\ n≡h (mod p) \end{matrix}} c_{n}e^{2πinx} = f_{p,h}(x).

This proves the lemma.

Lemma 2.4. Let α_{1}, α_{2}, …, α_{m} ∈ K, and let (n_{1}, …, n_{m}) ∈ ℤ^{m}. Then

|N(n_{1}α_{1} + ⋯ + n_{m}α_{m})| ≤ C(α_{1}, …, α_{m})( max_{1≤j≤m} |n_{j}|)^{m},

where C(∂_{1}, …, α_{m}) does not depend on n_{1}, …, n_{m}.

Proof. Since

N(n_{1}α_{1} + ⋯ + n_{m}α_{m}) = ∏_{σ} σ(n_{1}α_{1} + ⋯ + n_{m}α_{m}),

where σ runs through all isomorphisms of the field K into the field ℂ, we have

N(n_{1}α_{1} + ⋯ + n_{m}α_{m}) = ∏_{σ}(n_{1}σ(α_{1}) + ⋯ + n_{m}σ(α_{m})).

This proves the lemma.

Lemma 2.5. The norm of an integer divisor 𝔞 of the field K with respect to ℚ is equal to the number of residue classes of ℤ_{K} mod𝔞, i.e.,

N_{K/ℚ}(𝔞) = |ℤ_{K}/(𝔞)|,

where (𝔞) is the ideal of the ring ℤ_{K} consisting of all α ∈ ℤ_{K} which are divisible by 𝔞. The proof can be found in [1, p. 242]. Lemma 2.6. For any algebraic number field K, [K : ℚ]<∞, there exists a constant x_{0} =x_{0}(K)

such that

∑_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈ℙ \\ x<N(𝔭)≤2x \end{matrix}}1 ≥ \frac{9}{10} \frac{x}{ln x}

for all x ≥ x_{0}.

See the proof in [2, p. 345].

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

78 VORONIN

Lemma 2.7. Let ω_{1}, …, ω_{m} be the fundamental basis of the field K, 𝔭 ∈ ℙ_{K}, and let N(𝔭) = p ∈ ℙ. Then there exists a vector a ∈ ℤ^{m} such that

δ_{𝔭}(n_{1}ω_{1} + ⋯ + n_{m}ω_{m}) = \frac{1}{p} ∑_{νmodp} exp(2πi⟨a, n⟩\frac{ν}{p} )

for any n = (n_{1}, …, n_{m}) ∈ ℤ^{m}.

The proof is given in [3, p. 133].

3. FUNDAMENTAL LEMMAS

Lemma 3.1. Let M ⊂ ℤ, |M| ≥ 1, max_{m∈M} |m| ≤ N, L ≥ 2, and let

Q ≥ max(1000, 2L|M| ln(2N)).  (4)

Then there exists p ∈ ℙ such that (a) p ∈ (Q, 2Q];

(b) among the numbers h = 1, 2, ..., p there are no less than |M|(1 − \frac{2L + 1}{L(L + 1)}) numbers such

that

1 ≤ ∑_{\begin{matrix}n∈M \\ n≡h (mod p) \end{matrix}} 1 < L.

Proof. We set

M = ∏_{\begin{matrix}n_{1},n_{2}∈M \\ n_{1}≠n_{2} \end{matrix}} |n_{1} − n_{2}|  for |M| > 1  and  M = 1  for |M| = 1.  (5)

We have the estimate

M ≤ (2N)^{|M|^{2}} = exp(|M|^{2} ln(2N)).  (6)

Let

Z(M; p, h) = ∑_{\begin{matrix}n∈M \\ n≡h (mod p) \end{matrix}} 1.

We shall show that the inequality

ord_{p} M ≥ ∑_{h=1}^{p} Z^{2}(M; p, h) − |M|  (7)

holds for any p ∈ ℙ.

In fact, by the definition of Z(M; p, h) there are exactly Z^{2}(M; p, h) pairs among (n_{1}, n_{2}) ∈ M × M such that n_{1} ≡ n_{2} ≡ h (mod p). Therefore there exist exactly

∑_{h=1}^{p}(Z^{2}(M; p, h) − 1) = ∑_{h=1}^{p} Z^{2}(M; p, h) − |M|

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

factors in product (5) which are divisible by p. Therefore inequality (7) is proved in the case |M| > 1. Now if |M| = 1, then inequality (7) is obvious. Next, we shall show that there exists a number p ∈ ℙ such that

(a) the estimate

∑_{h=1}^{p} Z^{2}(M; p, h) ≤ (1 + \frac{1}{L})|M|  (8)

hold,

(b) p ∈ (Q, 2Q].

Assume the contrary. Then the inequality

∑_{h=1}^{p} Z^{2}(M; p, h) > (1 + \frac{1}{L})|M|

holds for all p ∈ (Q, 2Q]. Consequently, by inequality (7), the inequality

ord_{p} M ≥ ∑_{h=1}^{p} Z^{2}(M; p, h) − |M| > \frac{1}{L}|M|

holds for all p ∈ (Q, 2Q]. Therefore the relations

M ≥ ∏_{p∈(Q,2Q]} p^{ord_{p} M} > ∏_{p∈(Q,2Q]} p^{|M|/L} = ( ∏_{Q<p≤2Q} p)^{|M|/L} = exp(\frac{1}{L}|M|( ∑_{p∈(Q,2Q]} ln p)) (9)

hold. Since

∑_{Q<p≤2Q} ln p > \frac{1}{2}Q

by the Cebyshev theorem on the distribution of prime numbers in the series of positive integers (by virtue of the choice of Q), we infer from relations (9) that

M > exp(\frac{1}{2L}|M|Q).

By estimate (6), this implies the inequality

|M|^{2} ln(2N) > \frac{1}{2L}|M|Q.

Since by the hypothesis of Lemma 3.1, we have (4), we obtain a contradiction. Thus, we have proved the existence of p ∈ ℙ, p ∈ (Q, 2Q], such that estimate (8) is valid. We fix this p.

Let the set H ⊂ {1, 2, …, p} consists of those and only those h ∈ {1, 2, …, p} for which Z(M; p, h) ≠ 0, i.e., for these h there exists a number n ∈ M such that

n ≡ h (mod p).

Using the Cauchy inequality, we obtain

|M| = ∑_{h∈H} Z(M; p, h) = ∑_{h∈H} 1 × Z(M; p, h)

≤ |H|^{1/2}(∑_{h∈H} Z^{2}(M; p, h))^{1/2} ≤ |H|^{1/2}(∑_{h=1}^{p} Z^{2}(M; p, h))^{1/2}.

By estimate (8), this implies

|H| ≥ |M|^{2}(∑_{h=1}^{p} Z^{2}(M; p, h))^{−1} ≥ |M|^{2}(|M|(1 + \frac{1}{L}))^{−1} = |M|\frac{L}{L + 1}.  (10)

We set

H_{0} = {h : h ∈ H, Z(M; p, h) < L}.

In order to prove Lemma 3.1, it suffices to estimate |H_{0}| from below in an appropriate way. Note that the inequalities

|M| ≥ ∑_{h=1}^{p} Z(M; p, h) ≥ ∑_{h∈H\H_{0}} Z(M; p, h) ≥ L|H \ H_{0}|

hold, since, by the definition of H_{0}, we have Z(M; p, h) ≥ L for h ∈ H and h ∉ H_{0}. Therefore

|H \ H_{0}| ≤ |M|L^{−1}.  (11)

From inequalities (10) and (11) we find that

|H_{0}| = |H| − |H \ H_{0}| ≥ |M|\frac{L}{L + 1} − |M|L^{−1} = |M|(\frac{L}{L + 1} − \frac{1}{L}) = |M|(1 − \frac{2L + 1}{L(L + 1)}), (12)

and this proves the lemma.

Lemma 3.2. Let M ⊂ ℤ^{m}, 1 ≤ |M| < ∞. Assume that

N = max_{n=(n_{1},...,n_{m})∈M} max_{1≤j≤m} |n_{j}|,  L ≥ 2.

Then there exist two positive constants c_{0} and c_{1} which are dependent only on the field K and the fundamental basis ω_{1}, …, ω_{m} of the field K and are such that for any Q ≥ max(c_{1}, 2m|M| ln(c_{0}N)) there exists 𝔭 ∈ ℙ_{K} such that

(a) N(𝔭) = p ∈ (Q, 2Q];

(b) among the numbers h ∈ \{1, 2, ..., p\} there are no less than |M|(1 − \frac{2L + 1}{L(L + 1)}) numbers

for which

1 ≤ ∑_{\begin{matrix}n∈M \\ ñ≡h (mod 𝔭) \end{matrix}}1 < L.

Proof. We set

M = ∏_{\begin{matrix}n_{1},n_{2}∈M \\ n_{1}≠n_{2} \end{matrix}}(ñ_{1} − ñ_{2}).

Let us estimate |N(M)| from above. By Lemma 2.4, we have

|N(ñ_{1} − ñ_{2})| ≤ C(ω_{1}, …, ω_{m})(2N)^{m} ≤ (c_{0}N)^{m}.

Therefore

|N(M)| = ∏_{\begin{matrix}n_{1},n_{2}∈M \\ n_{1}≠n_{2} \end{matrix}} |N(ñ_{1} − ñ_{2})| ≤ (c_{0}N)^{m|M|^{2}}.  (13)

Let

Z(M; 𝔞, β) = ∑_{\begin{matrix}n∈M \\ ñ≡β (mod 𝔞) \end{matrix}}1

for 𝔞 ∈ D_{K} (D_{K} is an integer divisor of the field K) and β ∈ ℤ_{K}. We shall show that the inequality

ord_{𝔭} M ≥ ∑_{h=1}^{p} Z^{2}(M; 𝔭, h) − |M| ≥ 0  (14)

holds for any 𝔭 ∈ ℙ_{K}, N(𝔭) = p ∈ ℙ.

Indeed, if 𝔭 | h ∈ ℕ, then N(𝔭) = p is also a divisor of n. Consequently, the numbers 1, 2, …, p are incomparable mod 𝔭. By Lemma 2.5, the numbers 1, 2, …, p are the complete collection of representatives of all residue classes mod 𝔭. Furthermore, if ñ_{1} ≡ h (mod 𝔭) and ñ_{2} ≡ h (mod 𝔭) for h ∈ {1, 2, …, p}, then 𝔭 | ñ_{1} − ñ_{2}. Hence, there are at least

∑_{h=1}^{p} Z^{2}(M; 𝔭, h)

pairs among (n_{1}, n_{2}), n_{1}, n_{2} ∈ M, such that 𝔭 | ñ_{1} − ñ_{2}. Rejecting the pairs (n_{1}, n_{2}) for which n_{1} = n_{2}, we obtain the estimate

ord_{𝔭} M ≥ ∑_{h=1}^{p} Z^{2}(M; 𝔭, h) − |M|.

Finally, the inequality

Z^{2}(M; 𝔭, h) ≥ Z(M; 𝔭, h)

holds. Therefore

∑_{h=1}^{p} Z^{2}(M; 𝔭, h) − |M| ≥ ∑_{h=1}^{p} Z(M; 𝔭, h) − |M| = 0.

This completes the proof of inequality (14).

Let x_{0}(K) be defined as in the formulation of Lemma 2.6, and let the constant c_{0} = c_{0}(K) be defined just as in formula (13). Let us now prove that if

Q ≥ max(x_{0}(K), 2mL|M| ln(c_{0}N)),  (15)

82 VORONIN

then, among the divisors 𝔭 ∈ ℙ, N(𝔭) = p ∈ (Q, 2Q], there exists a prime divisor 𝔭, N(𝔭) = p, for which

∑_{h=1}^{p} Z^{2}(M; 𝔭, h) ≤ (1 + \frac{1}{L})|M|.  (16)

Indeed, assume the contrary. Then

∑_{h=1}^{p} Z^{2}(M; 𝔭, h) > (1 + \frac{1}{L})|M|

for all 𝔭 such that N(𝔭) = p ∈ (Q, 2Q]. In this case, it follows from formula (14) that

ord_{𝔭} M ≥ ∑_{h=1}^{p} Z^{2}(M; 𝔭, h) − |M| > L^{−1}|M|.

Therefore the divisor

𝔞 = ∏_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈(Q,2Q] \end{matrix}}𝔭^{[L^{−1}|M|]+1}

divides the divisor M, where [L^{−1}|M|] is the integer part of the number L^{−1}|M|. Therefore N(𝔞) | |N(M)|. Then we infer that

∏_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈(Q,2Q] \end{matrix}}|N(𝔭)|^{L^{−1}|M|} < |N(M)|,

and therefore

L^{−1}|M| ∑_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈(Q,2Q] \end{matrix}}ln |N(𝔭)| < ln |N(M)|.  (17)

By Lemma 2.6, we have

∑_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈(Q,2Q] \end{matrix}}ln N(𝔭) > ln Q \frac{9}{10} \frac{Q}{ln Q} = \frac{9}{10}Q

for Q > x_{0}(K).

On the other hand, by inequality (13), we have

ln |N(M)| ≤ m|M|^{2} ln(c_{0}N).

Therefore we infer from inequalities (17) and (15) that

\frac{9}{10}L^{−1}|M|Q < m|M|^{2} ln(c_{0}N),

and, hence,

\frac{9}{10}L^{−1}|M| × 2mL|M| ln(c_{0}N) < m|M|^{2} ln(c_{0}N),

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

i.e., 9/5 < 1. This is a contradiction.

The obtained contradiction proves the existence of 𝔭 ∈ ℙ_{K}, N(𝔭) = p ∈ (Q, 2Q], for which inequality (16) holds.

We fix this prime divisor 𝔭. Assume that the set H ⊂ {1, 2, …, p} consists of those and only those h for which Z(M; 𝔭, h) > 0. Let us estimate |H| from below. Using the Cauchy inequality, we obtain

|sM| = ∑_{h∈H} Z(M; 𝔭, h) = ∑_{h∈H} 1 × Z(M; 𝔭, h) ≤ (∑_{h∈H} 1)^{1/2}(∑_{h=1}^{p} Z^{2}(M; 𝔭, h))^{1/2}.

It follows from this relation that

|H| ≥ |M|^{2}(∑_{h=1}^{p} Z^{2}(M; 𝔭, h))^{−1}.  (18)

By inequality (16), it follows from inequality (18) that

|H| ≥ (\frac{L}{L + 1})|M|.  (19)

Let now

H_{0} = {h : h ∈ H, Z(M; 𝔭, h) < L}.

Let us estimate H_{0} from below. We have

|M| = ∑_{h=1}^{p} Z(M; 𝔭, h) ≥ ∑_{h∈H\H_{0}} Z(M; 𝔭, h) ≥ L|H \ H_{0}|.

Hence, the inequality

|H \ H_{0}| ≤ |M|L^{−1}  (20)

holds. Now we obtain (12) from inequalities (19) and (20). The lemma is proved.

4. PROOF OF THEOREM 1.1

We define the sets M_{1}, M_{2}, …, M_{k} ⊂ M_{0} and the prime numbers p_{1}, …, p_{k} ∈ (Q_{0}, 2Q_{0}] as follows. First, in the hypothesis of Lemma 3.1 we set M = M_{0}, L = ln(|M_{0}|+20), N = max_{n∈M_{0}} |n|, and Q = Q_{0}. By Lemma 3.1, there exist a prime number p_{1} ∈ (Q_{0}, 2Q_{0}] and a set M_{1} ⊂ M_{0} such that

(a) the estimate

|M_{0} \ M_{1}| ≤ |M_{0}|\frac{2L + 1}{L(L + 1)}

holds,

(b) for any n_{1} ∈ M_{1}, we have

1 ≤ |{n_{2} : n_{2} ∈ M_{0}, n_{2} ≡ n_{1} (mod p_{1})}| < L.

Next, in order to construct the set M_{2}, under the conditions of Lemma 3.1, we set

M = M_{0} \ M_{1},  L = ln(|M_{0}| + 20),  N = max_{n∈M_{0}} |n|,  Q = Q_{0}.

By Lemma 3.1, we find p_{2} ∈ (Q_{0}, 2Q_{0}] and M_{2} ⊂ M_{0} \ M_{1} such that

(a) |M_{0}(M_{1} \ M_{2})| ≤ |M_{0}|(\frac{2L + 1}{L(L + 1)})^{2},

(b) the inequalities

1 ≤ |{n_{2} : n_{2} ∈ M_{0} \ M_{1}, n_{2} ≡ n_{1} (mod p_{2})}| < L

hold for any n_{1} ∈ M_{2}. Proceeding in this way, we construct sets M_{1}, …, M_{k} ⊂ M_{0} and the prime numbers

p_{1}, …, p_{k} ∈ (Q_{0}, 2Q_{0}] with the following properties:

(a)

M_{j} ⊂ M_{0} \ ⋃_{l=1}^{j−1} M_{l}, M_{j} ≠ ∅, j = 1, 2, …, k,

(b) ⋃_{j=1}^{k} M_{j} = M_{0},

(c) |M_{0} \ ⋃_{j=1}^{l} M_{j}| ≤ |M_{0}|(\frac{2L + 1}{L(L + 1)})^{l}, l = 1, 2, …, k,

(d) for all n_{1} ∈ M_{l} we have

1 ≤ |{n_{2} : n_{2} ∈ M_{0} \ ⋃_{j=1}^{l−1} M_{j}, n_{2} ≡ n_{1} (mod p_{l})}| < L,  (21)

(e) for sufficiently large |M_{0}| we have

k ≪ \frac{ln |M_{0}|}{ln ln |M_{0}|}.  (22)

Indeed, since

\frac{2L + 1}{L(L + 1)} < 2L^{−1} < c < 1,

this process terminates at a certain k < ∞. Moreover, estimate (22) holds for a sufficiently large |M_{0}|.

Let us now define the operators P_{j}. Let

P_{j}: L_{M_{0}} \ ⋃_{l=1}^{j−1} M_{l} → L_{M_{j}}, j = 1, 2, …, k,

be the operator which put the Fourier polynomial

(P_{j}f)(x) = ∑_{n∈M_{j}} a_{n}e^{2πinx}

ON INTERPOLATION FORMULAS 85

into correspondence with the Fourier polynomial

f(x) = ∑ ; n∈M_{0}\⋃_{l=1}^{j−1} M_{l} a_{n}e^{2πinx}.

Let us analytically express P_{j}. For brevity of writing, we introduce the notation

M̃_{j} = M_{0} \ ⋃_{l=1}^{j−1} M_{l}.

Let

H^{(j)} = {h : h ∈ {1, 2, …, p_{j}}, h ∈ M_{j} (mod p_{j})},  (23)
M̃_{j,h} = {n : n ∈ M̃_{j}, n ≡ h (mod p_{j})},  (24)
P_{j,h}: LM̃_{j} → LM̃_{j,h},

where, for all f ∈ LM̃_{j},

f(x) = ∑_{n∈M̃_{j}} a_{n}e^{2πinx},  (25)

we set by definition

(P_{j,h}f)(x) = ∑_{\begin{matrix}n∈M̃_{j} \\ n≡h (mod p_{j}) \end{matrix}} a_{n}e^{2πinx}.  (26)

It follows from (23), (24), and (26) that

P_{j} = ∑_{h∈H^{(j)}} P_{j,h}.  (27)

Let h ∈ H^{(j)}, f_{j,h} ∈ LM̃_{j,h}, and let

M_{j,h} = \{ \begin{matrix}∏_{\begin{matrix}n_{1},n_{2}∈M̃_{j,h} \\ n_{1}≠n_{2} \end{matrix}} |n_{1} − n_{2}| & if |M_{j,h}| < 1 \\ 1 & if |M_{j,h}| = 1. \end{matrix}

We denote by q_{j}^{(h)} the minimal prime number which does not divide M_{j,h}. Then, by Lemma 2.2, we have the relation

f_{j,h}(x) = \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}} f_{j,h}(\frac{ν}{q_{j}^{(h)}} )DM̃_{j,h}(x − \frac{ν}{q_{j}^{(h)}} ).  (28)

Let us estimate q_{j}^{(h)} from above. Since n_{1}, n_{2} ∈ M̃_{j,h}, we have n_{1} ≡ n_{2} ≡ h (mod p_{j}). Since h ∈ H^{(j)}, we infer from relations (21) and (23) that 1 ≤ |M_{j,h}| < L.

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

Consequently, the estimate

M_{j,h} ≤ (2N + 3)^{L^{2}} = exp(L^{2} ln(2N + 3))

holds.

Let all prime numbers q ∈ (1, x] divide M_{j,h}. Then the inequality

∏_{\begin{matrix}q≤x \\ q∈ℙ \end{matrix}}q ≤ M_{j,h} ≤ (2N + 3)^{L^{2}},

must hold, and therefore the inequality

L^{2} ln(2N + 3) ≥ ∑_{q≤x} ln q  (29)

is valid. Using the Chebyshev theorem on the distribution of prime numbers in the series of positive integers, we obtain from relation (29) the inequality

x < max(1000, 2L^{2} ln(2N + 3)).

This implies that

q_{j}^{(h)} ≤ max(1000, 2L^{2} ln(2N + 3)) = max(1000, 2 ln^{2}(|M_{0}| + 20) ln(2N + 3)).  (30)

Note that estimate (30) does not depend on j and h only when h ∈ H^{(j)}.

Furthermore, by Lemma 2.3, the relation

(P_{j,h}f)(x) = \frac{1}{p_{j}} ∑_{ν=1}^{p_{j}} exp(−2πi\frac{hν}{p_{j}} )f(\frac{ν}{p_{j}} + x)

holds for f(x) ∈ LM̃_{j}. Therefore, it follows from formula (28) that

f_{j,h}(x) = (P_{j,h}f)(x) = \frac{1}{q_{j}^{(h)}} ∑_{ν_{h}=1}^{q_{j}^{(h)}}(P_{j,h}f)(\frac{ν_{h}}{q_{j}^{(h)}} )DM̃_{j,h}(x − \frac{ν_{h}}{q_{j}^{(h)}} )

= \frac{1}{q_{j}^{(h)}} ∑_{ν_{h}=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν=1}^{p_{j}} exp(−2πi\frac{hν}{p_{j}} )f(\frac{ν}{p_{j}} + \frac{ν_{h}}{q_{j}^{(h)}} ))DM̃_{j,h}(x − \frac{ν_{h}}{q_{j}^{(h)}} )

= \frac{1}{p_{j}q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} ∑_{ν_{h}=1}^{q_{j}^{(h)}} exp(−2πi\frac{hν}{p_{j}} )f(\frac{ν}{p_{j}} + \frac{ν_{h}}{q_{j}^{(h)}} )DM̃_{j,h}(x − \frac{ν_{h}}{q_{j}^{(h)}} ).  (31)

(The substitution of M_{j,h} for M̃_{j,h} in DM̃_{j,h}( ·) is possible since h ∈ M_{j} (mod p_{j}).)

Now it follows from (27) and (31) that

(P_{j,h}f)(x) = \frac{1}{p_{j}} ∑_{h∈H^{(j)}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} e^{−2πi \frac{hν}{p_{j}}} ∑_{ν_{h}=1}^{q_{j}^{(h)}} f(\frac{ν}{p_{j}} + \frac{ν_{h}}{q_{j}^{(h)}} )DM̃_{j,h}(x − \frac{ν_{h}}{q_{j}^{(h)}} ).  (32)

By construction, the operator P_{j} is defined on the space LM̃_{j}. For convenience, we extend

its definition to the space L_{M_{0}} with the use of formula (32). Let E denote the identity operator, E: L_{M_{0}} → L_{M_{0}}. By the definition of the linear operator P_{j},

(E − P_{j})f ∈ LM̃_{j+1}

for any Fourier polynomial (25), where f(x) ∈ LM̃_{j} (we use the convention LM̃_{k+1} = {0}). There-

fore the relation

(E − P_{k}) ⋯ (E − P_{1})|_{L_{M_{0}}} ≡ 0.  (33)

holds. We infer from (33) that

E = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{1}}.

Therefore, we have the following relation for f ∈ L_{M_{0}}:

f(x) = (Ef)(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k}(P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{1}}f)(x)

= ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k}((P_{j_{l}} ⋯ P_{j_{2}})P_{j_{1}}f)(x).  (34)

Expressing P_{j_{1}}f on the right-hand side with the aid of formula (32) of (34), we obtain

f(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} \frac{1}{p_{j_{1}}} ∑_{h∈H^{(h)}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{p_{j_{1}}} exp(−2πi\frac{hν}{p_{j_{1}}} )f(\frac{ν}{p_{j_{1}}} + \frac{κ}{q_{j_{1}}^{(h)}} )

× P_{j_{l}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{κ}{q_{j_{1}}^{(h)}} )(x).

The assertion of Theorem 1.1 follows from this formula.

5. PROOF OF THEOREM 1.2

In order to prove Theorem 1.2, we express

(P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{κ}{q_{j_{1}}^{(h)}} ))(x)

in terms of the characteristic functions of the arithmetic progressions, i.e., in terms of χ(a; q, b). We have

(P_{j_{l}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{κ}{q_{j_{1}}^{(h)}} ))(x) = ∑_{n_{1}∈M_{j_{1},h}} exp(−2πin_{1} \frac{κ}{q_{j_{1}}^{(h)}} )(P_{j_{l}} ⋯ P_{j_{2}} exp(2πin_{1}∗))(x).

From the definition of P_{j} we have (P_{j} exp(2πin_{1}∗))(x)

= \frac{1}{p_{j}} ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod p_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} exp(−2πi\frac{hν}{p_{j}} ) ∑_{κ=1}^{q_{j}^{(h)}}exp(2πin_{1}(\frac{ν}{p_{j}} + \frac{κ}{q_{j}^{(h)}} ))D_{M_{j},h}(x − \frac{κ}{q_{j}^{(h)}} )

= \frac{1}{p_{j}} ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod p_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} exp(−2πi\frac{hν}{p_{j}} ) ∑_{κ=1}^{q_{j}^{(h)}}exp(2πin_{1} \frac{ν}{p_{j}} ) exp(2πin_{1} \frac{κ}{q_{j}^{(h)}} )

× ∑_{n_{2}∈M_{j,h}} exp(2πin_{2}x) exp(−2πin_{2} \frac{κ}{q_{j}^{(h)}} )

= \frac{1}{p_{j}} ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod p_{j}) \end{matrix}}^{p_{j}} ∑_{n_{2}∈M_{j,h}} exp(2πin_{2}x)\frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{p_{j}} exp(2πi(n_{1} − h)\frac{ν}{p_{j}} ) ∑_{κ=1}^{q_{j}^{(h)}}exp(2πi(n_{1} − n_{2})\frac{κ}{q_{j}^{(h)}} )

= ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod p_{j}) \end{matrix}}^{p_{j}} ∑_{n_{2}∈M_{j,h}} χ(h; p_{j}, n_{1})χ(n_{1}; q_{j}^{(h)}, n_{2}) exp(2πin_{2}x).  (35)

Applying formula (35), we use iteration and obtain

(P_{j} … P_{j_{2}} exp(2πin_{1}∗))(x) = ∑_{\begin{matrix}h_{2}=1 \\ h_{2}∈M_{j_{2}} (mod p_{j_{2}}) \end{matrix}}^{p_{j_{2}}} ∑_{n_{2}∈M_{j_{2},h_{2}}} ⋯ ∑_{\begin{matrix}h_{l}=1 \\ h_{l}∈M_{j_{l}} (mod p_{j_{l}}) \end{matrix}}^{p_{j_{l}}} ∑_{n_{l}∈M_{j_{l},h_{l}}} χ(h_{2}; p_{j_{2}}, n_{1})

× χ(n_{1}; q_{j_{2}}^{(h_{2})}, n_{2})χ(h_{3}; p_{j_{3}}, n_{2})χ(n_{2}; q_{j_{3}}^{(h_{3})}, n_{3}) ⋯ χ(h_{l}; p_{j_{l}}, n_{l−1})χ(n_{l−1}; q_{j_{l}}^{(h_{l})}, n_{l}) exp(2πin_{l}x). (36)

Applying (36), we obtain the assertion of Theorem 1.2 from Theorem 1.1.

6. PROOF OF THEOREM 1.3

Using Lemma 3.2, we find prime divisors 𝔭_{1}, …, 𝔭_{k} and sets M_{1}, …, M_{k} ⊂ M_{0} such that (a) N(𝔭) = p_{j} ∈ ℙ for j = 1, …, k, p_{j} ∈ (Q, 2Q],

(b) M_{0} = ⋃_{j=1}^{k} M_{j},

(c) M_{j} ⊂ M_{0} \ (M_{1} ∪ ⋯ ∪ M_{j−1});

(d) if n_{1} ∈ M_{j}, then

1 ≤ |{n_{2} : ñ_{2} ≡ ñ_{1} (mod 𝔭_{j}), n_{2} ∈ M_{0} \ ⋃_{l=1}^{j−1} M_{l}}| < L.

We shall construct the sets M_{1}, M_{2}, … recursively. To this end, under the conditions of Lemma 3.2, we first set M = M_{0}, Q = Q_{0}, L = ln(|M_{0}| + 20) and find 𝔭_{1} and M_{1} possessing the corresponding properties. Next, setting M = M_{0} \ M_{1} and leaving Q and L invariant, we find 𝔭_{2} and M_{2}. We continue this process until we obtain an empty set. By Lemma 3.2, each operation of this kind diminishes M at least L/2 times. Hence, after

k ≪ \frac{ln(|M_{0}| + 20)}{ln ln(|M_{0}| + 20)}

steps, we obtain an empty set. We set

M̃_{j} = M_{0} \ ⋃_{l=1}^{j−1} M_{l},  M̃_{j,h} = {n : ñ ≡ h (mod 𝔭_{j}), n ∈ M̃_{j}}.

Let the linear operator P_{j} put the polynomial

(P_{j}f)(x) = ∑_{n∈M_{j}} a_{n} exp(2πi⟨n, x⟩)

into correspondence with the Fourier polynomial

f(x) = ∑_{n∈M̃_{j}} a_{n} exp(2πi⟨n, x⟩).  (37)

Since Im(E − P_{j}) ⊂ LM̃_{j+1}, we have

(E − P_{k})(E − P_{k−1}) ⋯ (E − P_{1})|_{L_{M_{0}}} = 0.  (38)

Furthermore, let

(P_{j,h})(x) = ∑_{n∈M̃_{j,h}} a_{n} exp(2πi⟨n, x⟩)

for polynomial (37). It follows from the definitions of P_{j} and P_{j,h} that

P_{j} = ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p}P_{j,h}.  (39)

Let us express P_{j,h} formally. Suppose that f ∈ LM̃_{j}, and let

f(x) = ∑_{n∈M̃_{j}} b_{n} exp(2πi⟨n, x⟩).

Then, by the definition of P_{j,h}, we have

(P_{j,h}f)(x) = ∑_{\begin{matrix}n∈M_{j} \\ ñ≡h (mod 𝔭_{j}) \end{matrix}}b_{n} exp(2πi⟨n, x⟩) = ∑_{n∈M̃_{j}} δ_{𝔭_{j}}(ñ − h)b_{n} exp(2πi⟨n, x⟩).  (40)

We use here Lemma 2.7. By Lemma 2.7, there exists a vector a_{j} ∈ ℤ^{m} such that for α ∈ ℤ_{K} we have

δ_{𝔭}(α) = \frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(2πi⟨\overline{α}, a_{j}⟩\frac{ν_{j}}{p_{j}} ),  (41)

where p_{j} = N(𝔭_{j}), and the vector \overline{α} can be found from the decomposition α = α_{1}ω_{1} + ⋯ + α_{m}ω_{m}, i.e., \overline{α} = (α_{1}, α_{2}, …, α_{m}). We find from relations (40) and (41) that

(P_{j,h}f)(x) = ∑_{n∈M̃_{j}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(2πi⟨n − \overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} ))b_{n} exp(2πi⟨n, x⟩)

= \frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} ) ∑_{n∈M̃_{j}} b_{n} exp(2πi⟨n, x + \frac{ν_{j}a_{j}}{p_{j}} ⟩).  (42)

Let h ∈ M_{j} (mod 𝔭_{j}), and let

M_{j,h} = \{ \begin{matrix}∏_{n_{1},n_{2}∈M̃_{j,h}}(ñ_{1} − ñ_{2}) & if |M_{j,h}| > 1 \\ 1 & if |sM_{j,h}| = 1. \end{matrix}

By the definition of the set M_{j}, we have 1 ≤ |M_{j,h}| < L for h ∈ M_{j} (mod 𝔭_{j}). Therefore it follows from Lemma 2.4 that

|N(M_{j,h})| = ∏_{n_{1},n_{2}∈M̃_{j,h}} |N(ñ_{1} − ñ_{2})| ≤ (CN^{m})^{L^{2}} = exp(L^{2}(m ln N + C)).  (43)

Assume that all 𝔭 ∈ ℙ_{K} such that N(𝔭) = p ∈ ℙ, p ≤ 2x, divide M_{j,h}. Then, by inequality (43), the inequalities

exp(ln x ∑_{\begin{matrix}𝔭∈ℙ \\ N(𝔭)=p∈ℙ \\ x<N(𝔭)≤2x \end{matrix}}1) ≤ exp( ∑_{\begin{matrix}𝔭∈ℙ_{K} \\ N(𝔭)=p∈ℙ \\ x<N(𝔭)≤2x \end{matrix}}ln p) ≤ exp(L^{2}(m ln N + C))  (44)

must be valid. By Lemma 2.6, it follows from inequality (44) that

\frac{9}{10}x ≤ L^{2}(m ln N + C).

We infer from this inequality that for a sufficiently large x_{0}, there exists a divisor 𝔮_{j}^{(h)} ∈ ℙ_{K},

N(𝔮_{j}^{(h)}) = q_{j}^{(h)} ∈ ℙ, for which

𝔮_{j}^{(h)} ∤ M_{j,h}

and

N(𝔮_{j}^{(h)}) = q_{j}^{(h)} < max(x_{0}, 4L^{2}(m ln N + C)).

Let

φ(x) = ∑_{n∈M_{j,h}} α_{n} exp(2πi⟨n, x⟩) ∈ L_{M_{j,h}}.

ON INTERPOLATION FORMULAS 91

Let us construct an interpolation formula for φ(x). We have

φ(x) = ∑_{n_{1}∈M_{j,h}} α_{n_{1}} ∑_{n∈M_{j,h}} δ(n − n_{1}) exp(2πi⟨n, x⟩).  (45)

Since 𝔮_{j}^{(h)} does not divide n − n_{1} for n ≠ n_{1}, it follows from (45) that

φ(x) = ∑_{n_{1}∈M_{j,h}} α_{n_{1}} ∑_{n∈M_{j,h}} δ_{𝔮_{j}^{(h)}}(ñ − ñ_{1}) exp(2πi⟨n, x⟩).  (46)

By Lemma 2.7, there exists a vector a_{j}^{(h)} ∈ ℤ^{m} such that

δ_{𝔮_{j}^{(h)}}(ñ − ñ_{1}) = \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}} exp(2πi⟨a_{j}^{(h)}, n_{1} − n⟩\frac{ν}{q_{j}^{(h)}} ).  (47)

We infer from formulas (46) and (47) that

φ(x) = ∑_{n_{1}∈M_{j,h}} α_{n_{1}} ∑_{n∈M_{j,h}}(\frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}} exp(2πi⟨a_{j}^{(h)}, n_{1} − n⟩\frac{ν}{q_{j}^{(h)}} ) exp(2πi⟨n, x⟩)

= \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}( ∑_{n_{1}∈M_{j,h}} α_{n_{1}} exp(2πi⟨a_{j}^{(h)}, n_{1}⟩\frac{ν}{q_{j}^{(h)}} ))( ∑_{n∈M_{j,h}} exp(2πi⟨n, x − a_{j}^{(h)} \frac{ν}{q_{j}^{(h)}} ⟩))

= \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}} φ(\frac{ν}{q_{j}^{(h)}} a_{j}^{(h)})D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}).  (48)

Since (P_{j,h}f)(x) ∈ L_{M_{j,h}}, it follows from formulas (42) and (48) that

(P_{j,h}f)(x) = \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(P_{j,h}f)(\frac{ν}{q_{j}^{(h)}} a_{j}^{(h)})D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)})

= \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} )

× ∑_{n∈M̃_{j}} b_{n} exp(2πi⟨n, \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{j}}{p_{j}} a_{j}⟩))D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}). (49)

It follows from relations (39) and (49) that

(P_{j}f)(x) = ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} )

× ∑_{n∈M̃_{j}} b_{n} exp(2πi⟨n, \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{j}}{p_{j}} a_{j}⟩))D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}).

We extend the definition of the operator P_{j} to the space L_{M_{0}} with the use of the formula

(P_{j}f)(x) = ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} )

× ∑_{n∈M_{0}} b_{n} exp(2πi⟨n, \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{j}}{p_{j}} a_{j}⟩))D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}).  (50)

Note that formula (38) is valid. Indeed, the operator P_{j} is applied to the function (E − P_{j−1}) × ⋯ (E − P_{1})f which belongs to the space LM̃_{j}. On the other hand, the extension of the domain of definition of the operators P_{j} gives us a possibility to open the brackets in relation (38).

Opening the brackets in relation (38), we obtain

E = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{1}}.

Hence, the identity

f(x) = (Ef)(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k}(P_{j_{l}} ⋯ P_{j_{1}}f)(x)

holds for every f ∈ L_{M_{0}}. Applying relation (50), we obtain

f(x) = ∑_{l=1}^{k}(−1)^{l−1} ∑_{1≤j_{1}<···<j_{l}≤k} ∑_{\begin{matrix}h=1 \\ h∈M_{j_{1}} (mod 𝔭_{j_{1}}) \end{matrix}}^{p_{j_{1}}} \frac{1}{q_{j_{1}}^{(h)}} ∑_{ν=1}^{q_{j_{1}}^{(h)}} \frac{1}{p_{j_{1}}} ∑_{ν_{1}modp_{j_{1}}} exp(−2πi⟨\overline{h}, a_{j_{1}}⟩\frac{ν_{1}}{p_{j_{1}}} )

× f(\frac{ν}{q_{j_{1}}^{(h)}} a_{j_{1}}^{(h)} + \frac{ν_{1}}{p_{j_{1}}} a_{j_{1}})(P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{ν}{q_{j_{1}}^{(h)}} a_{j_{1}}^{(h)}))(x).

We have thus proved Theorem 1.3.

7. PROOF OF THEOREM 1.4

To prove Theorem 1.4, it suffices to express

(P_{j_{l}}P_{j_{l−1}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{ν}{q_{j_{1}}^{(h)}} a_{j_{1}}^{(h)}))(x)

in terms of the characteristic functions of arithmetic progressions.

By the definition of D_{M}, we have

(P_{j_{l}} ⋯ P_{j_{2}}D_{M_{j_{1},h}}(∗ − \frac{ν}{q_{j_{1}}^{(h)}} a_{j_{1}}^{(h)}))(x)

= ∑_{n_{1}∈M_{j_{1},h}} exp(−2πi⟨n_{1}, \frac{ν}{q_{j_{1}}^{(h)}} a_{j_{1}}^{(h)}⟩)(P_{j_{l}} ⋯ P_{j_{2}} exp(2πi⟨n_{1}, ∗⟩))(x).

By the definition of the operator P_{j} (formula (50)), we have

(P_{j} exp(2πi⟨n, ∗⟩))(x) = ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} \frac{1}{q_{j}^{(h)}} ∑_{ν=1}^{q_{j}^{(h)}}(\frac{1}{p_{j}} ∑_{ν_{j} modp_{j}} exp(−2πi⟨\overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} )

× exp(2πi⟨n, \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)} + \frac{ν_{j}}{p_{j}} a_{j}⟩)D_{M_{j,h}}(x − \frac{ν}{q_{j}^{(h)}} a_{j}^{(h)}))

= \frac{1}{p_{j}} ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} ∑_{n_{1}∈M_{j,h}} exp(2πi⟨n_{1}, x⟩)\frac{1}{q_{j}^{(h)}}

× ∑_{ν_{j} modp_{j}} exp(2πi⟨n − \overline{h}, a_{j}⟩\frac{ν_{j}}{p_{j}} ) ∑_{νmodq_{j}^{(h)}} exp(2πi⟨n − n_{1}, a_{j}^{(h)}⟩\frac{ν}{q_{j}^{(h)}} )

= ∑_{\begin{matrix}h=1 \\ h∈M_{j} (mod 𝔭_{j}) \end{matrix}}^{p_{j}} ∑_{n_{1}∈M_{j,h}} δ_{p_{j}}(⟨n − \overline{h}, a_{j}⟩)δ_{q_{j}^{(h)}}(⟨n − n_{1}, a_{j}^{(h)}⟩) exp(2πi⟨n_{1}, x⟩).

(51)

Applying successively formula (51), we obtain

(P_{j_{l}} ⋯ P_{j_{2}} exp(2πi⟨n, ∗⟩))(x) = ∑_{\begin{matrix}h_{2}=1 \\ h_{2}∈M_{j_{2}} (mod 𝔭_{j_{2}}) \end{matrix}}^{p_{j_{2}}} ∑_{n_{2}∈M_{j_{2},h_{2}}} ⋯ ∑_{\begin{matrix}h_{l}=1 \\ h_{l}∈M_{j_{l}} (mod 𝔭_{j_{l}}) \end{matrix}}^{p_{j_{l}}} ∑_{n_{l}∈M_{j_{l},h_{l}}}
× δ_{p_{j_{2}}} (⟨n − \overline{h}_{2}, a_{j_{2}}⟩)δ_{q_{j_{2}}^{(h_{2})}}(⟨n − n_{2}, a_{j_{2}}^{(h_{2})}⟩)
× δ_{p_{j_{3}}} (⟨n_{2} − \overline{h}_{3}, a_{j_{3}}⟩)δ_{q_{j_{3}}^{(h_{3})}}(⟨n_{2} − n_{3}, a_{j_{3}}^{(h_{3})}⟩) ⋯

× δ_{p_{j_{l}}} (⟨n_{l−1} − \overline{h}_{l}, a_{j_{l}}⟩)δ_{q_{j_{l}}^{(h_{l})}}(⟨n_{l−1} − n_{l}, a_{j_{l}}^{(h_{l})}⟩) exp(2πi⟨n_{l}, x⟩).

(52)

The assertion of Theorem 1.4 follows from Theorem 1.3 and formula (52).

ACKNOWLEDGMENTS

This work was supported by the Russian Foundation for Fundamental Research (project no. 96-01-00767).

REFERENCES

1. Borevich, Z. I. and Shafarevich, I. R., Teoriya chisel (Number Theory), Moscow: Nauka, 1985.

2. Algebraic Number Theory (Cassels, J. and Frölich, A., Eds.), London, 1967.

3. Voronin, S. M., On Quadrature Formulas, Izv. Russian Akad. Nauk, Ser. Mat., 1994, vol. 58, no. 5, pp. 189–194. Translated by S. Vakhromeev