Estimates on the tail distribution of Gaussian polynomials. The discussion of a result of Latała.

Péter Major Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences Budapest, P.O.B. 127 H–1364, Hungary, e-mail: major@renyi.hu

Summary: In this paper a result of Latała about the tail behaviour of Gaussian polynomials will be discussed. Latała proved an interesting result about this problem in paper [3]. But his proof contained some essential gaps at certain points. In this paper I want to fill these gaps. Beside this I try to present such an explanation that reveals the ideas behind the proofs better than the original paper.

1. Introduction. Formulation of the main results.

In this paper the following problem studied in Latała’s paper [3] will be revisited.

Let us have a multilinear form

\begin{aligned}A(u_{1}, …, u_{d}) & = A(d)(u_{1}, …, u_{d}) \\ & = ∑_{(i_{1},...,i_{d}): 1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d})u_{1}(i_{1}) ⋯ u_{d}(i_{d}) \end{aligned}  (1.1)

of order d in the space of vectors (u_{1}, …, u_{d}) where u_{j} = (u_{j}(1), …, u_{j}(n_{j})) ∈ R^{n_{j}}, and R^{n_{j}} is the Euclidean space with some prescribed dimension n_{j}, 1 ≤ j ≤ d, defined with the help of a set of real numbers A(d) = A(d|n_{1}, …, n_{d}) = {a(i_{1}, …, i_{d}), 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d}.

Beside this, let us also have d independent standard Gaussian random vectors G_{j} = (g_{j}(1), …, g_{j}(n_{j})) of dimension n_{j}, 1 ≤ j ≤ d, and define with the help of the multilinear form (1.1) and these Gaussian random vectors the Gaussian random polynomial

Y (A) = Y (A(d)) = ∑_{(i_{1},...,i_{d}): 1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d})g_{1}(i_{1}) … g_{d}(i_{d})  (1.2)

of order d. We want to give a good estimate on the tail distribution P (|Y (A)| > x) for all x > 0 under appropriate conditions on the multilinear form A(·) defined in (1.1). Naturally, it belongs to the problem to find the right conditions under which useful results can be proved.

Some estimates can be proved about the tail distribution of Gaussian polynomials and so-called degenerate U-statistics under the condition that their variance is bounded by a known constant, (see [5]), and these results are in a sense sharp. On the other hand, they can be improved if we have some additional useful information about the behaviour of the multi-linear form (1.1). Latała proved an interesting result in this direction in paper [3]. He found the right conditions under which a good estimate can be given about the tail-distribution P (|Y (A)| > x). Similar questions can be also asked about degenerate U-statistics, and Adamczak proved in [1] some results in this direction. But the essential step in the study of such problems is to find the proof (and formulation) of the right estimates for the tail distribution of Gaussian polynomials. The adaptation of such results to U-statistics is rather a technical problem.

Hence I restrict my attention to Latała’s work. I discuss its proof and present a version of it, because I found an error in paper [3] that caused serious problems for me. For a long time I even doubted the validity of the main result in [3]. My problems were related to the proof of Theorem 3 in [3]. It was based on a backward induction procedure with respect to a parameter l. The induction steps when we turn from l + 1 to l were explained for all parameters l ≥ 1. But the final step when we turn from l = 1 to l = 0 was not considered in the proof. This error seemed to be crucial for me for a long time. Then it turned out that this error can be corrected. But to do this I had to work out many details which were only sketched in the original proof. This is done in this paper. Beside this I made some efforts to reveal the ideas behind the steps of the proof.

To formulate Latała’s result I introduce some notations. Let us define the linear functional

A(v) = A(d, v) = ∑_{(i_{1},...,i_{d}): 1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d})v(i_{1}, ⋯, i_{d})  (1.3)

in the space of all real valued functions v(i_{1}, …, i_{d}) defined on the n-tuples (i_{1}, …, i_{d}), 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d, where the coefficients a(i_{1}, …, i_{d}) agree with those in (1.1)

Let us also introduce the class P = P_{d} of all partitions of the set {1, …, d}. We shall define a class of finite sequences of functions with the help of these partitions, and the conditions of Latała’s result will be formulated with their help. To avoid some repetitions in further discussions I define these quantities in a slightly more general form.

Let us have a finite subset K ⊂ {1, 2, …, } of the positive integers together with a function b_{K}(i_{j}, j ∈ K), 1 ≤ i_{j} ≤ n_{j}, j ∈ K, and the numbers n_{j}, j ∈ K, which tell which values the arguments of the function B_{K}(i_{j}, j ∈ K, 1 ≤ j ≤ n_{j}, j ∈ K) can take. We define with their help, similarly to the quantity A(v), the linear functional

B_{K}(v) = ∑_{(i_{j}, j∈K): 1≤i_{j}≤n_{j}, j∈K} b_{K}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ K)v(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ K)

(1.4)

in the space of functions v(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ K).

Let P(K) denote the set of all partitions of the set K, and given a partition P = {A_{1}, …, A_{s}} ∈ P(K) of s elements together with the positive integers n_{j}, j ∈ K, appearing in the definition of the sets P (K) let us define with their help the following set G_{P} of sequences of functions (v_{1}, v_{2}, …, v_{s}):

\begin{aligned}G_{P} & = \{(v_{1}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ A_{1}), …, v_{s}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ A_{s})): \\ & ∑_{(i_{1},...,i_{j}): 1≤i_{j}≤n_{j}, j∈A_{r}} v_{r}^{2}(i_{j}, j ∈ A_{r}) ≤ 1 for all 1 ≤ r ≤ s\} \end{aligned}  (1.5)

if P = {A_{1}, …, A_{s}} ∈ P(K). Let us have a linear functional B_{K}(v) of the form (1.4) together with the coefficients b_{K}(·) taking part in its definition. Then we define with the help of the class of functions G_{P} defined in (1.5) the following quantity V (P, B_{K}) for all partitions P ∈ P(K).

\begin{matrix}V (P, B_{K}) = V (P, b_{K}(·)) \\ = sup_{(v_{1},...,v_{s})∈G_{P}} ∑ b_{K}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ K) ∏_{1≤r≤s} v_{r}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ A_{r}). \end{matrix}

(1.6)

for a partition P = {A_{1}, …, A_{s}} ∈ P(K). In this formula the same coefficients b_{K}(i_{j}, 1 ≤ i_{j} ≤ n_{j}, j ∈ K) appear as in (1.4).

Given a partition P = {A_{1}, …, A_{s}} ∈ P(K) let |P | = s denote its cardinality. In the remaining part of this section I restrict my attention to partitions P ∈ P_{d} of the set {1, …, d} and to the case when the linear functional A(v) defined in formula (1.3) is considered. In this case the quantity introduced in (1.6) will be denoted as V (P, A) = V (P, (a(·)). Let us define with its help the numbers

α_{s} = α_{s}(A) = sup_{P: P ∈P_{d}, |P |=s} V (P, A) for all 1 ≤ s ≤ d.  (1.7)

The main result of Latała we discuss in this paper can be formulated with the help of the quantities α_{s}, 1 ≤ s ≤ d, introduced in (1.7). It states the following inequalities.

Theorem 1. The moments of the Gaussian random polynomial Y (A(d)) defined in formula (1.2) satisfy the inequality

E(Y (A(d)))^{2M} ≤ (C(d) max_{1≤s≤d}(M^{s/2}α_{s}))^{2M}  (1.8)

for all d ≥ 2 and M = 1, 2, … with the quantities α_{s} defined in (1.7) and a constant C(d) depending only on the order d of the Gaussian polynomial Y (A(d)). As a consequence,

P (|Y (A(d))| > x) ≤ C(d) exp \{−\frac{1}{C(d)} min_{1≤s≤d} (\frac{x}{α_{s}} )^{2/s}\}  (1.9)

for all d ≥ 2 and x > 0 with some constant C(d) depending only on d.

Remark 1. Latała’s paper also contains a similar lower bound for the moments and probabilities in (1.8) and (1.9). These bounds state that the estimates in this formulas are essentially sharp, only the value of the parameter C(d) can be improved in them. The proof of these lower bounds is considerably simpler. Since their proof in [3] is correct, I shall omit their discussion.

Remark 2. In the subsequent estimations some constants C, C_{1}, C(d) etc. will appear in different formulas. The same letter may denote different constants in different formulas. It will be important that these constants are universal, depending at least of the order d of the Gaussian polynomial we are considering. There will be some places in our discussion where the constants in different formulas have to be compared. The necessary considerations will be taken at these points.

Remark 3. The dimension n_{j} of the Euclidean spaces R^{n_{j}} where the appropriate vectors take their values plays no role in our considerations. It is exploited in some arguments that they are finite, but their value will be not important for us. At several points where it makes no problem I shall omit the parameters n_{j} from the formulas. By means of some limiting procedure one can get results in the case when n_{j} = ∞, i.e. when we consider infinite series of independent standard Gaussian random variables instead of Gaussian polynomials in (1.2).

Remark 4. Another interesting modification of Theorem 1 is the result one gets when such random polynomials are estimated where the independent Gaussian random vectors G_{j} = (g_{j}(1), …, g_{j}(n_{j})), 1 ≤ j ≤ d, in formula (1.2) are replaced by such Gaussian random vectors G_{j} which consist of the first n_{j} elements of the same sequence G = (g(1), g(2), …), of independent standard normal random variables for all 1 ≤ j ≤ d. An estimate similar to Theorem 1 for such modified Gaussian random polynomials can be obtained by means of paper [2]. The main difference between the original and the new result is that in the new case so-called Wick polynomials take the role of traditional polynomials. Wick polynomials are the natural multivariate versions of Hermite polynomials. The appearance of Wick polynomials in this result is related to the fact that paper [2] deals only with U-statistics. Hence the result of this paper can be applied only for such Gaussian polynomials Y (A) defined in (1.2) where summation is taken for coordinates (i_{1}, …, i_{d}) with the restriction i_{j} ≠ i_{j′} if j ≠ j′. One can get rid of this restriction in the summation by means of an appropriate limiting procedure during which the Wick polynomials appear. I do not discuss here the details of such a procedure.

In the following Theorem 1A I formulate a formally weaker version of Theorem 1. But actually, as I shall show these two results are equivalent. Since Theorem 1A is technically simpler, this result will be proved.

Theorem 1A. Let the Gaussian polynomial Y (A(d)), d ≥ 2, defined in (1.2) be such that the expressions α_{s}, 1 ≤ s ≤ d, defined in (1.7) satisfy the inequality

α_{s} = α_{s}(A) ≤ M^{−(s−1)/2} for all 1 ≤ s ≤ d  (1.10)

with some positive integer M. Then

EY (A(d))^{2M} ≤ C(d)^{M}M^{M}  (1.11)

with a constant C(d) > 0 depending only on the order d of the Gaussian polynomial Y (A(d)).

Theorem 1A states that if a Gaussian polynomial Y (A(d)) satisfies condition (1.10) then its 2M-th moment satisfies such an estimate as the 2M-th moment of a standard normal random variables multiplied by a constant.

The deduction of Theorem 1 from Theorem 1A. Let us consider the random variable Y (A(d)) and the number 2M which is the moment we consider in formula (1.8). Let us define with their help the constant D(M) = max_{1≤s≤d}(M^{(s−1)/2}α_{s}) and introduce

the Gaussian polynomial D(M)^{−1}Y (A(d)) defined in formula (1.2) with coefficients D(M)^{−1}a(i_{1}, …, i_{d}). This polynomial satisfies relation (1.10), hence by Theorem 1A relation (1.11) also holds for it. This means that EY (A(d))^{2M} ≤ (C(d)D(M)^{2}M)^{M} which is equivalent to relation (1.8) in Theorem 1.

Relation (1.9) follows from relation (1.8) in the standard way. By the Markov inequality P (|Y (A(d))| ≥ x) ≤ x^{−2M}EY (A(d))^{2M} for arbitrary M = 1, 2, . . .. Choose

M = [ min_{1≤s≤d} \frac{1}{KC(d)} \frac{x}{α_{s}} ]^{2/s} if x ≥ KC(d) min_{1≤s≤d} α_{s}, where [·] denotes integer part, C(d) is

the same constant which appears in (1.8), and K = K(d) is a sufficiently large constant depending only on d. In this case we get from relation (1.8) that P (|Y (A(d))| ≥ x) ≤ e^{−M} which implies relation (1.9) with the constant K^{2}C(d)^{2} if x ≥ KC(d) min_{1≤s≤d} α_{s}.

On the other hand, if x ≤ KC(d) min_{1≤s≤d} α_{s}, and the constant K was chosen sufficiently

large, then the right-hand side of relation (1.9) (with the previously chosen constant K^{2}C^{2}(d) as the number ‘C(d)’ in (1.9)) is larger than 1. Hence relation (1.9) holds also in this case.

This paper consists of eight sections and an Appendix. In Section 2 the proof of Theorem 1A is reduced to a result called the Basic estimate by means of a conditioning argument. In Section 3 this Basic estimate is proved in the special case d = 2. In Section 4 a result of paper [3] is recalled about the estimation of the cardinality of an appropriate ε-net in a metric space with some nice properties. In Section 5 a result called the Main inequality is presented, and it is shown that the Basic estimate follows from it. In Section 6 two results, Lemma 6.1 and Lemma 6.2 are formulated. They provide a good partition of certain sets of functions which play crucial role in the proof of the Main inequality. The proof of these lemmas is based on some estimates formulated in Lemma 6.3. Lemma 6.3 together with its proof is also given in Section 6. Lemmas 6.1 and 6.2 are proved in Section 7. Finally the Main inequality is proved in Section 8 by means of the results in Section 6. Since in Section 4 I apply a terminology essentially different from that of [3] I found better not to refer to the original proofs of the results presented here, but to describe them instead. This is done in the Appendix. In such a way I wanted to make this paper self-contained.

The proofs of this paper apply several ideas of Paper [3]. But since the notation and the formulation of the results in these two works are very different, and the main ideas in [3] are presented in a rather hidden way I only explain which results of these two paper correspond to each other.

2. The application of a conditioning argument.

In this section a conditioning argument is applied to reduce the proof of Theorem 1A to the verification of a result called the Basic estimate.

To carry out this conditioning argument let us define the Gaussian random vector

Y_{d}(u) = Y_{d}(u, A) = ∑_{(i_{1},...,i_{d}): 1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d})u_{1}(i_{1}) … u_{d−1}(i_{d−1})g_{d}(i_{d})

(2.1)

for all vectors u = (u_{1}, …, u_{d−1}), u_{j} = (u_{j}(1), …, u_{j}(n_{j})), 1 ≤ j ≤ d − 1, and a standard Gaussian vector G_{d} = (g_{d}(i_{1}), …, g_{d}(n_{d})). The coefficients a(i_{1}, …, i_{d}) in formulas (1.1) and (2.1) are the same. Actually in formula (2.1) we took the multilinear form (1.1) and replaced the vector u_{d} by the standard normal random vector G_{d} in it.

We want to estimate the moments of the random variables Y (A(d)) introduced in (1.2). This can be done by means of the following conditioning argument.

E(Y (A(d))^{2M}|g_{d}(1) = u_{d}(1), …, g_{d}(n_{d}) = u_{d}(n_{d}))

= E ( ∑_{(i_{1},...,i_{d}): 1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d})g_{1}(i_{1}) … g_{d−1}(i_{d−1})u_{d}(i_{d}))^{2M} .

Hence

EY (A(d))^{2M} = EY (A(d), M, G_{d})  (2.2)

where

\begin{matrix}Y (A(d), M, u_{d}) \\ = E [ ∑_{i_{d}=1}^{n_{d}} ( ∑_{(i_{1},...,i_{d−1}): 1≤i_{j}≤n_{j}, 1≤j≤d−1}a(i_{1}, …, i_{d})g_{1}(i_{1}) … g_{d−1}(i_{d−1})) u_{d}(i_{d})]^{2M} , \end{matrix}

or in an equivalent form

\begin{matrix}Y (A(d), M, u_{d}) \\ = E ( ∑_{(i_{1},...,i_{d−1}): 1≤i_{j}≤n_{j}, 1≤j≤d−1} b_{u_{d}}(i_{1}, …, i_{d−1})g_{1}(i_{1}) … g_{d−1}(i_{d−1}))^{2M} , \end{matrix}

(2.3) with

b_{u_{d}}(i_{1}, …, i_{d−1}) = ∑_{i_{d}=1}^{n_{d}} a(i_{1}, …, i_{d})u_{d}(i_{d}),  (2.4)

where u_{d} = (u_{d}(1), …, u_{d}(n_{d})) is an arbitrary vector in R^{n_{d}}.

Next I formulate a result called the Basic estimate. Its proof will be the main subject of the subsequent sections. Here I prove that Theorem 1A follows from it. To formulate the Basic estimate first I introduce the following quantity.

Z_{d} = Z_{d}(A) = sup_{u=(u_{1},...,u_{d−1}): u_{j}∈B^{n_{j}} , 1≤j≤d−1} Y_{d}(u),  (2.5)

where the (Gaussian) random variables Y_{d}(u) were defined in (2.1). Here and in the subsequent part of the paper B^{n} denotes the unit ball in the Euclidean space R^{n} with

the usual Euclidean norm, i.e. B^{n} = {(u(1), …, u(n)): ∑_{j=1}^{n} u(j)^{2} ≤ 1}. It will be shown

that Theorem 1A follows from the following result.

Basic estimate. If the linear form A(v), d ≥ 2, introduced in (1.3) is such that the quantities α_{s} defined in (1.7) satisfy the condition (1.10) with some positive integer M, i.e. α_{s} = α_{s}(A) ≤ M^{−(s−1)/2} for all 1 ≤ s ≤ d, then the estimate

EZ_{d}^{2M} = EZ_{d}(A)^{2M} ≤ C^{M}M^{−(d−2)M}  (2.6)

holds with a constant C = C(d) depending only on d.

Remark. The above formulated Basic estimate is closely related to Theorem 2 in [3]. The main difference between them is that Theorem 2 in [3] gives an estimate only for the expected value EZ_{d}(A) of Z_{d}(A) and not for its higher moments. Thus our result is,

— at least formally, — sharper. But actually estimate (2.6) follows from the result of [3] and an important concentration inequality of Ledoux about the supremum of Gaussian random variables. This result will be recalled in Section 3. The reason for the present formulation of the Basic estimate was that I wanted to show that the so-called chaining argument applied in its proof also supplies the estimate (2.6) for d ≥ 3, i.e. we do not need Ledoux’s inequality in this case. Surprisingly, we need it just in the simplest case d = 2, when the proof is given by means of a simple and natural direct calculation instead of the chaining argument.

We shall estimate EY (A(d))^{2M} with the help of relations (2.2) and (2.3) by induction with respect to d for all d ≥ 2. Let us first consider the case d = 2.

If the linear form A(2)(u_{1}, u_{2}) in (1.1) (with d = 2) is defined with the help of a set of numbers {a(i, j) 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ n_{2}}, then we can write

Y (A(2), M, u_{2}) = E [∑_{i=1}^{n_{1}} (∑_{j=1}^{n_{2}} a(i, j)u_{2}(j)) g_{1}(i)]^{2M}

= 1 · 3 · · · · · (2M − 1) (E [∑_{i=1}^{n_{1}} (∑_{j=1}^{n_{2}} a(i, j)u_{2}(j)) g_{1}(i)]^{2})^{M}

= 1 · 3 · · · · · (2M − 1) (∑_{i=1}^{n_{1}} (∑_{j=1}^{n_{2}} a(i, j)u_{2}(j))^{2})^{M}  (2.7)

= 1 · 3 · · · · · (2M − 1) ( sup_{u_{1}=(u_{1}(1),...,u_{1}(n_{1})): u_{1}∈B^{n_{1}}} ∑_{i=1}^{n_{1}} ∑_{j=1}^{n_{2}} a(i, j)u_{1}(i)u_{2}(j))^{2M} ,

where u_{2} = (u_{2}(1), …, u_{2}(n_{2}) ∈ R^{n_{2}}, u_{1} = (u_{1}(1), …, u_{1}(n_{1})) ∈ B^{n_{1}}, and B^{n_{1}} denotes

the unit ball of the Euclidean space R^{n_{1}}, i.e. we demand that ∑_{i=1}^{n_{1}} u_{1}(i)^{2} ≤ 1. By

relations (2.2), (2.7), the definition of the quantity Z_{d}(A) and the Basic estimate

EY_{2}(A(2))^{2M} ≤ (2M)^{M}EZ_{2}(A(2))^{2M} ≤ CM^{M}

if α_{1}(A) ≤ 1 and α_{2}(A) ≤ M^{−1/2}, i.e. if the conditions of the Basic estimate hold for d = 2. Thus we have proved Theorem 1A with the help of the Basic estimate in the case d = 2.

In the case d ≥ 3 Theorem 1A will be proved by means of induction. During this induction procedure we assume that Theorem 1A holds for 2 ≤ d′ ≤ d − 1, and the Basic estimate holds for 2 ≤ d′ ≤ d.

First the expression Y (A(d), M, u_{d}) will be estimated. This expression, defined in (2.3) is the 2M-th moment of a Gaussian polynomial of order d − 1 which is defined similarly to Y (A) introduced in formula (1.2) only with the coefficients b_{u_{d}}(i_{1}, …, i_{d−1}) introduced in (2.4) instead of a(i_{1}, …, i_{d}). Hence, as we shall show, they satisfy the following inequality.

\begin{aligned}Y (A(d), M, u_{d}) & ≤ max_{P ∈P_{d−1}} (V (P, B_{u_{d}})^{2}M^{(|P |−1)})^{M} (CM)^{M} \\ & ≤ C^{M} ∑_{P ∈P_{d−1}} V (P, B_{u_{d}})^{2M}M^{|P |M} \end{aligned}  (2.8)

with some constant C = C(d), where V (P, B_{u_{d}}) was defined in (1.6) for partitions P ∈ P_{d−1} i.e. K = {1, …, d − 1}, and the numbers b_{u_{d}}(i_{1}, …, i_{d−1}) introduced in (2.4) play the role of the coefficients b_{K}(·) in formulas (1.4) and (1.6).

Indeed, the expression _{\frac{Y (A(d),M,u_{d})}{max_{P ∈P_{d−1}}(V (P,B_{u_{d}})M^{(|P |−1)/2})^{2M}}} equals the 2M-th moment of

such a Gaussian polynomial which satisfies the conditions of Theorem 1A with parameter d − 1. Hence Theorem 1A with parameter d − 1 (which holds by our induction hypothesis) implies the first inequality in (2.8). The second inequality of (2.8) is obvious.

By relations (2.2) and (2.8)

EY (A(d))^{2M} ≤ C^{M} ∑_{P ∈P_{d−1}} EV (P, B_{G_{d}})^{2M}M^{|P |M},

where V (P, B_{G_{d}}) is the random variable we get by replacing the vector u_{d} by the random vector G_{d} = (g_{d}(1), …, g_{d}(n_{d})) in the expression V (P, B_{u_{d}}). Hence to complete the proof of the Theorem 1A it is enough to show that under the conditions of Theorem 1A

EV (P, B_{G_{d}})^{2M} ≤ C^{M}M^{−(|P |−1)M} for all P ∈ P({1, …, d − 1})  (2.9)

with a constant C = C(d). This result can be proved with the help of the Basic estimate.

To prove formula (2.9) take a partition P = {A_{1}, …, A_{s}} ∈ P_{d−1} with |P | = s elements. With such a choice

V (P, B_{G_{d}}) = sup_{(v_{1},...,v_{s})∈G_{P}} ∑_{(i_{1},...,i_{d})} a(i_{1}, …, i_{d}) ∏_{r=1}^{s} v_{r}(i_{j}, j ∈ A_{r})g_{d}(i_{d}).  (2.10)

In formula (2.10) the class of functions G_{P} where the supremum is taken is defined in (1.5) with the partition P we have fixed, and (g_{d}(1), …, g_{d}(n_{d})) is an n_{d} dimensional standard normal vector. The 2M-th moment of the right-hand side expression in (2.10) can be bounded by means of the Basic estimate with s+1 = |P |+1 ≤ d parameters (i.e. the number |P | + 1 takes the role of the parameter d in this case) if the vectors (i_{j}, j ∈ A_{r}), A_{r} ∈ P, are considered as one variable for all 1 ≤ r ≤ s. The condition of the Basic estimate formulated in (1.10) holds with such a choice, and we get inequality (2.9) in such a way.

We have reduced the problem we want to solve to the proof of an inequality formulated in the Basic estimate, where certain moments of a supremum sup_{u∈B^{n_{1}} ×···×B^{n_{d−1}}} Y_{d}(u)

of Gaussian random variables are bounded. The random variables Y_{d}(u) in this formula were defined in (2.1), and B^{n} denotes the unit ball in R^{n}. In the study of such problems it is worth introducing the metric ρ(u, v) = [E(Y_{d}(u) − Y_{d}(v))^{2}]^{1/2} on the parameter set of the random variables we are considering. This leads to the definition of the following pseudometric ρ_{α} in the space R^{n_{1}} × ⋯ × R^{n_{d−1}}.

\begin{aligned}ρ_{α}(u, v) & = ρ_{α}((u_{1}, …, u_{d−1}), (v_{1}, …, v_{d−1})) \\ & = [E(Y_{d}(u) − Y_{d}(v))^{2}]^{1/2} = E(E[  ∑_{1≤i_{j}≤n_{j}, 1≤j≤d} a(i_{1}, …, i_{d}) \\ & (u_{1}(i_{1}) ⋯ u_{d−1}(i_{d−1}) − v_{1}(i_{1}) ⋯ v_{d−1}(i_{d−1}))g(i_{d})]^{2})^{1/2} \\ & = ( ∑_{1≤i_{d}≤n_{d}}[ ∑_{1≤i_{j}≤n_{j}, 1≤j≤d−1} a(i_{1}, …, i_{d}) \\ & (u_{1}(i_{1}) ⋯ u_{d−1}(i_{d−1}) − v_{1}(i_{1}) ⋯ v_{d−1}(i_{d−1}))]^{2})^{1/2} \end{aligned} (2.11)

for all pairs of vectors u = (u_{1}, …, u_{d−1}) and v = (v_{1}, …, v_{d−1}), u_{j} ∈ R^{n_{j}}, v_{j} ∈ R^{n_{j}}, 1 ≤ j ≤ d − 1.

It is useful to give a different characterization of the above introduced metric ρ_{α}. For this goal let us define the pseudonorm α

\begin{aligned}α(v) & = α_{d}(v) = α_{d}(v(i_{1}, …, i_{d−1})) \\ & = [ ∑_{1≤i_{d}≤n_{d}}(  ∑_{1≤i_{j}≤n_{j}, 1≤j≤d−1} a(i_{1}, …, i_{d})v(i_{1}, ⋯, i_{d−1}))^{2}]^{1/2} \end{aligned}  (2.12)

in the linear space of the functions v = v(i_{1}, …, i_{d−1}), 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d − 1. Clearly,

ρ_{α}((u_{1}, …, u_{d−1}), (v_{1}, …, v_{d−1})) = α_{d}(u_{1} ⊗ ⋯ ⊗ u_{d−1} − v_{1} ⊗ ⋯ ⊗ v_{d−1}) (2.13)

where the function u_{1} ⊗ ⋯ ⊗ u_{d−1} with arguments (i_{1}, …, i_{d−1}), 1 ≤ i_{j} ≤ n_{j} for all 1 ≤ j ≤ d − 1 is defined as u_{1} ⊗ ⋯ ⊗ u_{d−1}(i_{1}, …, i_{d−1}) = u_{1}(i_{1}) ⋯ u_{d−1}(i_{d−1}), and v_{1} ⊗ ⋯ ⊗ v_{d−1} is defined similarly.

The above representation of the metric ρ_{α} turned out to be useful. In the study of the Basic estimate we have to find a good ε-net for certain subsets of B^{n_{1}} × ⋯ × B^{n_{d−1}} with respect to the metric ρ_{α} for small ε > 0. The representation of the metric ρ_{α} by formulas (2.12) and (2.13) may help in finding good ε-nets. This question will be discussed in detail in the subsequent sections. But before doing it I prove the Basic estimate together with some related results we need in our discussion in the special case d = 2. This case is considered separately, because the formulation of the results and their proof for d = 2 are slightly different from those in the general case.

3. The proof for Gaussian polynomials of order 2.

In this section the Basic estimate will be proved for Gaussian polynomials of order d = 2. It will be proved as the consequence of a more general result called the Main inequality in the case d = 2. A result called the Main inequality will be formulated in Section 5 for all dimensions d ≥ 3. The crucial point in the proof of Theorem 1A is the verification of this result. The Main inequality in the case d = 2 formulated in this section can be considered as a version of this result. But there are some differences between their formulation, and they must be considered separately. The Basic estimate for d = 2 could have been proved directly. I prove it with the help of the Main inequality in the case d = 2, because the latter result is also needed in the discussion of the case d ≥ 3. To formulate it I introduce some notations.

We shall work with some expressions A(v) and Y_{2} which are the quantities defined in (1.3) and (2.1) in the special case d = 2. Let us write them down in more detail.

These terms depend on a set of numbers A = A(2) = {a(i, j), 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ n_{2}}. The first of them is the linear functional

A(v) = A(2, v) = ∑_{i,j} a(i, j)v(i, j)

in the space of all functions v(i, j) with arguments 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ n_{2}. This is the expression (1.3) in the case d = 2. The expression (2.1) can be written as

Y (u) = Y_{2}(u) = ∑_{i,j} a(i, j)u(i)g_{2}(j),

with u = (u(1), …, u(n_{1})), where (g_{2}(1), …, g_{2}(n_{2})) is a standard normal random vector.

Let us observe that in the case d = 2 the quantity α_{1}(A) defined in (1.7) can be written as

α_{1}(A) = sup_{v(i,j): ∑_{i,j} v(i,j)^{2}≤1} ∑_{i,j} a(i, j)v(i, j) = (∑_{i,j} a(i, j)^{2})^{1/2} .  (3.1)

Let us also introduce the function

α_{2}(u) = [∑_{j} (∑_{i} a(i, j)u(i))^{2}]^{1/2} = sup_{v=(v(1),...,v(n_{2})): ∑_{j} v(j)^{2}≤1} ∑_{i,j} a(i, j)u(i)v(j)

for all vectors u = (u(1), …, u(n_{1})) ∈ R^{n_{1}}.

Let us fix some positive integer M, and define for all N ≥ 0 the following subset U_{N} = U_{N}(M) of R^{n_{1}}.

U_{N} = U_{N}(M) = {u = (u(1), …, u(n_{1})): u ∈ B^{n_{1}}, and α_{2}(u) ≤ 2^{−N}M^{−1/2}}. (3.2)

I formulate with the help of the above notations the following result.

The Main inequality in the case d = 2. Let α_{1}(A) ≤ 1. Then the inequality

E [ sup_{u: u∈U_{N}} Y (u)]^{2^{2(N+A)}M} ≤ (C · 2^{A})^{2^{2(N+A)}M}  (3.3)

holds for all integers N ≥ 0, M ≥ 1 and A ≥ 1 with C = 2, where the sets U_{N} were defined in (3.2).

Proof of the Main inequality in the case d = 2. This result will be proved with the help of the concentration inequality of Ledoux about the supremum of Gaussian random variables. (See [4] Theorem 7.1.) First I show that under the condition α_{1}(A) ≤ 1

E (  sup_{u=(u(1),...,u(n_{1})): ∑_{i=1}^{n_{1}} u(i)^{2}≤1} Y (u)) ≤ 1.  (3.4)

Indeed, for all ω ∈ Ω

sup_{∑_{i} u(i)^{2}≤1} ∑_{i,j} a(i, j)u(i)g(j)(ω) = [∑_{i} (∑_{j} a(i, j)g(j)(ω))^{2}]^{1/2} ,

since the above expression takes its supremum at the value

u(i) = \frac{∑_{j} a(i, j)g(j)(ω)}{[∑_{i} (∑_{j} a(i, j)g(j)(ω))^{2}]^{1/2}} , 1 ≤ i ≤ n_{1}.

Hence by the Schwarz inequality and relation (3.1)

E ( sup_{u=(u(1),...,u(n_{1})): ∑_{i} u(i)^{2}≤1} Y (u)) = E ( sup_{∑_{i} u(i)^{2}≤1} ∑_{i,j} a(i, j)u(i)g(j))

= E [∑_{i} (∑_{j} a(i, j)g(j))^{2}]^{1/2} ≤ [E ∑_{i} (∑_{j} a(i, j)g(j))^{2}]^{1/2}

= (∑_{i,j} a(i, j)^{2})^{1/2} = α_{1}(A) ≤ 1.

On the other hand EY (u) = 0 and EY (u)^{2} = α_{2}(u)^{2} ≤ 2^{−2N}M^{−1}, for all u ∈ U_{N}. Hence Ledoux’s concentration inequality (see formula 7.4 in [4]) implies that

P ( sup_{u∈U_{N}} |Y (u) − E sup_{u∈U_{N}} Y (u)| ≥ x) ≤ 2e^{−2^{−2N−1}Mx^{2}} for all x ≥ 0.

The above inequality with partial integration yield for all R ≥ 2 that

E sup_{u∈U_{N}} |Y (u) − E sup_{u∈U_{N}} Y (u)|^{2R} ≤ ∫_{0}^{∞} 2e^{−2^{2N−1}Mx^{2}} dx^{2R}

= 4R · 2^{−2NR}M^{−R} ∫_{0}^{∞} x^{2R−1}e^{−x^{2}/2} dx = 4R · 2^{−2NR}M^{−R}(2R − 2)(2R − 4) ⋯ 2

≤ (2RM^{−1})^{R}2^{−2NR} = (2RM^{−1}2^{−2N})^{R}.

Relation (3.3) follows from the above inequality with the choice 2R = 2^{2(N+A)}M, N ≥ 0, M ≥ 1, A ≥ 1, and the inequality E sup_{u∈U_{N}} Y (u) ≤ 1 which is a consequence of

relation (3.4).

Proof of the Basic estimate for d = 2. Let us apply the Main inequality in the case d = 2 with N = 0 and A = 1. Since the conditions of the Basic estimate for d = 2 contain the inequality α_{2}(A) = sup_{u∈B^{n_{1}}} α_{2}(u) ≤ M^{−1/2} the set U_{0} agrees with the unit

ball B^{n_{1}}. Hence the Schwarz inequality and relation (3.3) with the choice N = 0 and A = 1 yield the estimate

E [ sup_{u: u∈B^{n_{1}}} ∑_{i,j} a(i, j)u(i)g(j)]^{2M} ≤ (E [ sup_{u: u∈U_{0}} ∑_{i,j} a(i, j)u(i)g(j)]^{4M} )^{1/2}

≤ 4^{4M/2} = 2^{4M}.

The Basic estimate for d = 2 (with C = 16 in formula (2.6)) is proved.

4. Estimates on the cardinality of ε-nets with respect to nice metrics.

In the Basic estimate the moments of the supremum of a class of Gaussian random variables are estimated. In such problems it is worth introducing a natural metric on the set of parameters of the random variables we are considering, by defining the distance of two points in the parameter space as the square root of the variance of the difference of the corresponding random variables. It is also useful to find such a subset of the parameter space with relatively small cardinality which is dense with respect to this metric. Such an approach leads to the formulation of the following problem.

Given a pseudometric space (X, ρ) together with a subset X_{0} ⊂ X we want to find for all ε > 0 an ε-net of relatively small cardinality in the space X_{0} with respect to the metric ρ, i.e. we want to find a set {x_{1}, …, x_{N}} ⊂ X_{0} with a relatively small index N for which min_{1≤j≤N} ρ(x_{j}, x) ≤ ε for all x ∈ X_{0}. A good ε-net can be found by solving

the following problem. Let us define an appropriate probability measure μ in the space (X, ρ) and give a good lower bound on the probability μ({y: y ∈ X, ρ(y, x) ≤ ε}) for all x ∈ X_{0} and ε > 0.

Latała presented two estimates of this kind in Lemmas 1 and 2 of his paper [3]. In Lemma 1 that case is considered when X is the n-dimensional Euclidean space R^{n}, X_{0} is the unit ball in this space with respect to the Euclidean metric, and the pseudometric ρ = ρ_{α} is defined by means of a pseudonorm α in R^{n} in the usual way, i.e. ρ_{α}(x, y) = α(x − y). Lemma 2 is a multi-linear version of this result. Here the space X is the product of some Euclidean spaces. We embed it in the tensor product of these Euclidean spaces in a natural way, and the metric ρ_{α} in X is defined with the help of a pseudonorm in this tensor product.

Since these results play an important role in our considerations I recall them in this paper under the names Proposition 4.1 and Proposition 4.2. I shall apply a notation different from [3], and it may be hard to compare the results formulated here with their original version. Hence to make this paper self-contained I present the proof of Latała’s results in an Appendix.

To formulate these results some notations have to be introduced. We denote the unit ball in the n-dimensional Euclidean space by B^{n}. We introduce a probability measure μ_{n,t} depending on a parameter t in the Euclidean space R^{n} in the following way. Given some number t > 0 let μ_{n,t} denote the distribution of the random vector tG = (tg_{1}, …, tg_{n}) in R^{n}, where g_{1}, …, g_{n} are independent standard normal random variables.

Proposition 4.1. Let α_{1} and α_{2} be two pseudonorms in R^{n}, t > 0 an arbitrary positive number, x ∈ B^{n} a vector in the unit ball of R^{n} and G = (g_{1}, …, g_{n}) an n-dimensional standard normal vector. Then

μ_{n,t}(\{y: y ∈ R^{n}, α_{1}(y − x) ≤ 4Eα_{1}(tG), α_{2}(y − x) ≤ 4Eα_{2}(tG)\}) ≥ \frac{1}{2}e^{−1/2t^{2}}

with the above introduced probability measure μ_{n,t}.

Remark. In our applications it would be enough to consider a simpler version of Proposition 4.1 where only one pseudonorm α_{1} appears. We formulated a result with two pseudonorm, because such a result is applied in the proof of Proposition 4.2.

To formulate Proposition 4.2 some additional notations have to be introduced. Let us consider d Euclidean spaces R^{n_{1}}, …, R^{n_{d}} of dimension n_{j}, 1 ≤ j ≤ d, their product R^{n_{1}} × ⋯ × R^{n_{d}} and their tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} with some pseudonorm α(·) in the tensor product. We give an embedding of the product R^{n_{1}} × ⋯ × R^{n_{d}} of these Euclidean spaces into their tensor product and define with its help a pseudometric ρ_{α} in the product space R^{n_{1}} × ⋯ × R^{n_{d}} induced by the pseudonorm α in the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}}.

For the sake of simpler notations we shall represent the Euclidean space R^{n} as the space of the real valued functions x = (x(1), …, x(n)) on the set {1, …, n}, the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} of the Euclidean spaces R^{n_{j}}, 1 ≤ j ≤ d, as the space of the real valued functions v(i_{1}, …, i_{d}), defined on the set of vectors (i_{1}, …, i_{d}), 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d, and the product R^{n_{1}} × ⋯ × R^{n_{d}} as the space of all vectors x = (x_{1}, …, x_{d}), whose elements are real valued functions x_{j} = (x_{j}(1), …, x_{j}(n_{j})) on the sets {1, …, n_{j}}, 1 ≤ j ≤ d.

We embed the Euclidean space R^{n_{1}} ×⋯×R^{n_{d}} in the tensor product R^{n_{1}} ⊗⋯⊗R^{n_{d}} with the help of the map A(x) = A(x_{1}, …, x_{d}) = x_{1} ⊗⋯⊗x_{d} from the Euclidean space R^{n_{1}} × ⋯ × R^{n_{d}} into the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}}, where x_{1} ⊗ ⋯ ⊗ x_{d} is defined for a vector x = (x_{1}, …, x_{d}) ∈ R^{n_{1}} ×⋯×R^{n_{d}} by the formula x_{1} ⊗⋯⊗x_{d}(i_{1}, …, i_{d}) = x_{1}(i_{1}) ⋯ x_{d}(i_{d}) for all coordinates (i_{1}, …, i_{d}) with 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d.

Given a pseudonorm α on the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} define with its help the pseudometric ρ_{α} in the space R^{n_{1}} × ⋯ × R^{n_{d}} by the formula

ρ_{α}((x_{1}, … x_{d}), (y_{1}, …, y_{d})) = α(x_{1} ⊗ ⋯ ⊗ x_{d} − y_{1} ⊗ ⋯ ⊗ y_{d})  (4.1)

for all x = (x_{1}, …, x_{d}) ∈ R^{n_{1}} × ⋯ × R^{n_{d}} and y = (y_{1}, …, y_{d}) ∈ R^{n_{1}} × ⋯ × R^{n_{d}}. I shall call this ρ_{α} the pseudometric induced by the pseudonorm α.

Let us fix some x = (x_{1}, …, x_{d}) ∈ B^{n_{1}} × ⋯ × B^{n_{d}} in the product of the unit balls B^{n_{j}} in R^{n_{j}}, 1 ≤ j ≤ d. In Proposition 4.2 a good lower bound is given on the probability of a small neighbourhood of such a point x with respect to an appropriately defined probability measure. More explicitly, the probability μ_{n_{1}+···+n_{d},t}(y: y ∈ R^{n_{1}} × ⋯ × R^{n_{d}}, ρ_{α}(x, y) ≤ u) will be bounded from below for all numbers u > 0 with respect to an appropriately defined Gaussian measure μ_{n_{1}+···+n_{d},t}, where ρ_{α} is the pseudometric in R^{n_{1}} × ⋯ × R^{n_{d}} induced by a pseudonorm α in R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} by formula (4.1). To formulate this result some additional notations will be introduced.

Let us consider d independent standard normal vectors G_{j} = (g_{j}(1), …, g_{j}(n_{j})) of dimension n_{j}, 1 ≤ j ≤ d, and for all t > 0 let μ_{n_{1}+···+n_{d},t} denote the distribution of the random vector (tG_{1}, …, tG_{d}) in the space R^{n_{1}} × ⋯ × R^{n_{d}}. Given a pseudonorm α on the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} of the spaces R^{n_{j}}, 1 ≤ j ≤ d, a number t > 0, some set I ⊂ {1, …, d}, I ≠ ∅ and a vector x = (x_{1}, …, x_{d}) ∈ R^{n_{1}} × ⋯ × R^{n_{d}} we define the quantity

W_{I}^{x}(α, t) = Eα(z_{1} ⊗ ⋯ ⊗ z_{d}) where z_{j} = x_{j} if j ∉ I and z_{j} = tG_{j} if j ∈ I (4.2)

with the previously defined function z_{1} ⊗ ⋯ ⊗ z_{d} ∈ R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} for (z_{1}, …, z_{d}) ∈ R^{n_{1}} ×⋯×R^{n_{d}}. In words, we take the function α(x_{1} ⊗⋯⊗x_{d}), replace the coordinates x_{j} ∈ R^{n_{j}} by tG_{j} ∈ R^{n_{j}} for the indices j ∈ I, and take the expected value of the random variable obtained in such a way. With the help of the above quantities we can formulate Proposition 4.2.

Proposition 4.2. Let us have a pseudometric ρ_{α} in the product R^{n_{1}} × ⋯ × R^{n_{d}} of some Euclidean spaces R^{n_{j}}, 1 ≤ j ≤ d, induced by a pseudonorm α in their tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}}. Fix some vector x = (x_{1}, …, x_{d}) ∈ B^{n_{1}} × ⋯ × B^{n_{d}}, in the product of the unit balls B^{n_{j}} in R^{n_{j}}, 1 ≤ j ≤ d. The following inequality holds for such a vector x and an arbitrary number t > 0.

\begin{aligned}μ_{n_{1}+···+n_{d},t} & (\{y: y ∈ R^{n_{1}} × ⋯ × R^{n_{d}}, ρ_{α}(x, y) ≤ ∑_{I: I⊂\{1,...,d\}, I≠∅} W_{I}^{x}(α, 4t)\}) \\ & ≥ 2^{−d}e^{−d/2t^{2}} \end{aligned}

(4.3)

with the Gaussian probability measure μ_{n_{1}+···+n_{d},t} defined above.

The following corollary of Proposition 4.2 is important for us.

Corollary of Proposition 4.2. Let us have a pseudometric ρ_{α} in R^{n_{1}} × ⋯ × R^{n_{d}} induced by a pseudonorm α in the tensor product R^{n_{1}} ⊗⋯⊗R^{n_{d}} of the Euclidean spaces R^{n_{j}}, 1 ≤ j ≤ d. Let D ⊂ B^{n_{1}} × ⋯ × B^{n_{d}} be a subset of the product of the unit balls B^{n_{j}}, 1 ≤ j ≤ d that has the following property: ∑_{I⊂{1,...,d}, I≠∅} W_{I}^{x}(α, 4t) ≤ u with some

fixed numbers 0 < t ≤ 1 and u > 0 for all x ∈ D.

Then there is a constant C > 0 depending only on the parameter d such that the set D has a 2u-net of cardinality e^{C/t^{2}} with respect to the pseudometric ρ_{α}. In more detail this means that there is a set {x^{(1)}, …, x^{(N)}} ⊂ D with cardinality less than N ≤ e^{C/t^{2}} such that min_{1≤j≤N} ρ_{α}(x, x^{(j)}) ≤ 2u for all x ∈ D. As a consequence the set D has a

partition U_{1}, …, U_{N} with N ≤ 2^{C/t^{2}} elements such that the diameter of all sets U_{j}, 1 ≤ j ≤ N, is less than or equal to 4u with respect to the pseudometric ρ_{α}.

Proof of the Corollary. Let us construct a sequence x^{(1)}, x^{(2)}, …, x^{(N)}, x^{(j)} ∈ D, 1 ≤ j ≤ N, in the following way. Let us choose first a point x^{(1)} ∈ D in an arbitrary way. If the points x^{(1)}, …, x^{(j)} are already chosen, and there are some points x ∈ D such that ρ_{α}(x, x^{(p)}) > 2u for all 1 ≤ p ≤ j, then we choose an arbitrary point x ∈ D with this property as x^{(j+1)}. If there is no such point, then we finish our procedure at the j-th step. Let N be the number of points x^{(j)} that we could choose in such a way. Observe that the sets U_{j} = {y: y ∈ R^{n_{1}} ×⋯×R^{n_{d}}, ρ_{α}(y, x^{(j)}) ≤ u}, 1 ≤ j ≤ N, are disjoint, because ρ_{α}(x_{j}, x_{j′}) > 2u for all 1 ≤ j, j′ ≤ N, j ≠ j′. Beside this, μ_{n_{1}+···+n_{d},t}(U_{j}) ≥ 2^{−d}e^{−d/2t^{2}} by Proposition 4.2 for all 1 ≤ j ≤ N. Hence N ≤ 2^{d}e^{d/2t^{2}} ≤ e^{C/t^{2}}. Beside this, the set {x^{(1)}, …, x^{(N)}} is a 2u-net in D, because if there were a point x ∈ D such that min_{1≤j≤N} ρ_{α}(x, x^{(j)}) > 2u then we would not finish our procedure at the N-th step.

The balls R_{j} = {y: y ∈ D, ρ(y, x_{j}) ≤ 2u}, 1 ≤ j ≤ N, provide a covering of D with sets of diameter less than or equal to 4u with respect to the pseudometric ρ_{α}. The sets

U_{1} = R_{1}, U_{j} = R_{j} \ ⋃_{l=1}^{j−1} R_{l}, 2 ≤ j ≤ N, provide a partition with the desired properties.

Remark. In the proof of the above corollary we applied a rather standard method, wellknown in the literature. In general applications of a result similar to Proposition 4.2 the cardinality of a good ε-net of the set B^{n_{1}} × ⋯ × B^{n_{d}} is bounded. Here a slightly more general result was proved. This corollary gave an estimate about the cardinality of a good ε-net of an arbitrary set D ⊂ B^{n_{1}} × ⋯ × B^{n_{d}}. For some sets D with nice properties it provides a much better bound for the cardinality of a good ε-net in D than for the cardinality of a good ε-net in B^{n_{1}} ×⋯×B^{n_{d}}. This observation will be exploited in our further considerations.

In formula (2.11) we defined a pseudometric ρ_{α} in the product R^{n_{1}} × ⋯ × R^{n_{d−1}} of the Euclidean spaces R^{n_{j}}, 1 ≤ j ≤ n and in formula (2.12) a pseudonorm α in their tensor product R^{n_{1}} ⊗⋯⊗R^{n_{d−1}}. A comparison of formulas (2.13) and (4.1) shows that Proposition 4.2 and its corollary can be applied (with parameter d − 1) for the metric ρ_{α} and norm α defined in (2.11) and (2.12). This fact plays an important role in the proof of the Basic estimate.

5. The Main inequality.

In this section I formulate a result that I call the Main inequality and show that the Basic estimate and in such a way Theorem 1 follows from it. This result is a weaker version of an inductive statement formulated in the proof of Theorem 3 in [3].

To formulate this result let us fix the parameter d ≥ 3. We shall define appropriate classes U(r, N) of finite subsets of R^{n_{1}} × ⋯ × R^{n_{d−1}} which depend on two parameters N and r and have some nice properties. The Main inequality yields an estimate on the moments of the random variables sup_{u∈U, u′∈U}[Y_{d}(u) − Y_{d}(u′)] for the sets U ∈ U(r, N),

where Y_{d}(u) with parameter u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} is the Gaussian random variable defined in (2.1). To define these classes of sets U(r, N) some additional quantities have to be introduced.

We shall work with the linear functional A(v) = A(v, d) defined for functions v ∈ R^{n_{1}} ⊗⋯⊗R^{n_{d}} in formula (1.3) with the help of a set of numbers A = {a(i_{1}, …, i_{d}), 1 ≤ i_{p} ≤ n_{p}, 1 ≤ p ≤ d}. Let us also recall the definition of the Gaussian random variables Y_{d}(u) defined in (2.1) for vectors u = (u_{1}, …, u_{d−1}) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} together with a standard Gaussian random vector G_{d} = (g_{d}(1), …, g_{d}(n_{d})). We shall also work with the quantity ρ_{α}(u, v), u ∈ R^{n_{1}} ×⋯×R^{n_{d−1}} and v ∈ R^{n_{1}} ×⋯×R^{n_{d−1}} defined in (2.11).

Beside this, to define the sets U(r, N) we still have to introduce some pseudonorms α̃_{j,k} in the spaces R^{n_{j}} for all pairs j, k such that 1 ≤ j, k ≤ d − 1, j ≠ k, with the help of the coefficients a(i_{1}, …, i_{d}) appearing in formula (1.3).

For this goal first we introduce the set of constants

\begin{aligned}b_{u_{j}}^{(j)}(i_{1}, …, i_{j−1}, i_{j+1}, …, i_{d}) & = ∑_{i_{j}: 1≤i_{j}≤n_{j}} a(i_{1}, …, i_{d})u_{j}(i_{j}), \\ & 1 ≤ i_{p} ≤ n_{p}, p ∈ \{1, …, d\} \ \{j\}, \end{aligned}  (5.1)

for all vectors u_{j} ∈ R^{n_{j}} and the functional

B_{u_{j}}^{(j)}(v) = ∑_{\begin{matrix}(i_{1},...,i_{j−1},i_{j+1},...,i_{d}) \\ 1≤i_{p}≤n_{p}, p∈\{1,...,d\}\\{j\} \end{matrix}} b_{u_{j}}^{(j)}(i_{1}, …, i_{j−1}, i_{j+1}, …, i_{d})v(i_{1}, …, i_{j−1}, i_{j+1}, …, i_{d})

(5.2)

depending on this u_{j} ∈ R^{n_{j}} for all v ∈ R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{j−1}} ⊗ R^{n_{j+1}} ⊗ ⋯ ⊗ R^{n_{d}}. The functional B_{u_{j}}^{(j)}(v) defined in (5.2) is a special case of the operator B_{K}(v) introduced in (1.4) if we choose K = {1, …, d} \ {j} and the coefficient b_{K}(·) are chosen as the numbers b_{u_{j}}^{(j)}(·) introduced in (5.1). With such a choice we can introduce the quantity V (P, B_{u_{j}}^{(j)}) = V (P, b_{u_{j}}^{(j)}(·)) for all partitions P of the set {1, …, d} \ {j} as the quantity V (P, B_{K}) = V (P, b_{K}(·)) defined in (1.6) with this choice K = {1, …, d} \ {j} and B_{K}(v) = B_{u_{j}}^{(j)}(v). Let P_{j,k} denote the partition P_{j,k} = {{k, d}, {l}, 1 ≤ l ≤ d−1, l ≠ j, k} of the set {1, …, d} \ {j}, and define

α̃_{j,k}(u_{j}) = V (P_{j,k}, B_{u_{j}}^{(j)}), 1 ≤ j, k ≤ d − 1, k ≠ j, u_{j} ∈ R^{n_{j}}.  (5.3)

It is easy to check that α̃_{j,k}(u_{j}) is a pseudonorm in R^{n_{j}}.

The expression α̃_{j,k}(u_{j}) can also be written as

\begin{aligned}α̃_{j,k}(u_{j}) = & sup_{\begin{matrix}v_{p}(·), p∈\{1,...,d−1\}\\{j,k\}, v_{k,d}(·,·): \\ ∑_{ip} v_{p}^{2}(i_{p})≤1, p∈\{1,...,d−1\}\\{j,k\}, ∑_{i_{k},i_{d}} v^{2}(i_{k},i_{d})≤1, \end{matrix}} ∑_{i_{1},...,i_{d}} a(i_{1}, …, i_{d})u_{j}(i_{j}) \\ & v(i_{k}, i_{d}) ∏_{p∈\{1,...,d−1\}\\{j,k\}} v_{p}(i_{p}) \end{aligned} (5.4)

for any u_{j} = (u_{j}(1), …, u_{j}(n_{j})) ∈ R^{n_{j}}.

Given an operator A(v) of order d, d ≥ 3, defined in (1.3) and a positive integer M the following classes of sets U(r, N) = U_{A,M,d}(r, N) consisting of at most r elements u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} will be introduced.

U(r, N) = U_{A,M,d}(r, N)
= {U = {(u^{(t)} = (u_{1}^{(t)}, …, u_{d−1}^{(t)}) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}}, 1 ≤ t ≤ r′}:

1 ≤ r′ ≤ r, α̃_{j,k}(u_{j}^{(t)}) ≤ 2^{−N}M^{−(d−2)/2}, for all 1 ≤ t ≤ r′
and 1 ≤ j, k ≤ d − 1, j ≠ k,  (5.5)
ρ_{α}(u^{(t)}, u^{(t′)}) ≤ 2^{−2N}M^{−(d−1)/2} for all 1 ≤ t, t′ ≤ r′,
u^{(t)} ∈ B^{n_{1}} × ⋯ × B^{n_{d−1}}, for all 1 ≤ t ≤ r′,
u^{(t)} − u^{(t′)} ∈ B^{n_{1}} × ⋯ × B^{n_{d−1}} for all 1 ≤ t, t′ ≤ r′}

with the above defined α̃_{j,k} and the quantity ρ_{α}(·, ·) introduced in (2.11).

In the Main inequality we shall prove a moment estimate for the supremum of some random variables determined with the help of the sets U ∈ U(r, N). It holds under the condition

α_{s} = α_{s}(A) ≤ M^{−(s−1)/2}, for all 1 ≤ s ≤ d − 1,  (5.6)

where the quantities α_{s} were defined in (1.7).

Remark. In Theorem 1A we imposed a similar but stronger condition in formula (1.10). It also contained the condition α_{d} ≤ M^{−(d−1)/2} for s = d. This condition is missing here. It is replaced by the inequalities imposed on ρ_{α} in the definition of the classes of sets U(r, N). The additional condition of Theorem 1A is needed when we want to prove the Basic estimate with the help of the Main inequality.

The Main inequality. Let a multilinear form A of order d ≥ 3 satisfy condition (5.6). Take a standard normal random vector G_{d} = (g_{d}(1), …, g_{d}(n_{d})) of dimension n_{d}, and introduce with its help the random variables Y_{d}(u) defined in (2.1) for all vectors u = (u_{1}, …, u_{d−1}), u_{p} = (u_{p}(1), …, u_{p}(n_{p})) ∈ R^{n_{p}}, 1 ≤ p ≤ d − 1. There is a threshold index A_{0} ≥ 0 and a constant C > 0 such that for integers r ≥ 1 and N ≥ 0 the inequality

E [ sup_{\begin{matrix}u^{(t)}=(u_{1}^{(t)},...,u_{d−1}^{(t)})∈U, \\ u^{(t′)}=(u_{1}^{(t′)},...,u_{d−1}^{(t′)})∈U \end{matrix}}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))]^{2^{2(N+A)}M}≤ (CM^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}

(5.7)

holds for all U ∈ U(r, N) and integers A ≥ A_{0}. The numbers A_{0} = A_{0}(d) and C = C(d) are sufficiently large constants which depend only on d and do not depend on the parameters r and N.

Let us understand the content of the Main inequality. It provides good estimates for the moments of the random variables sup_{u^{(t)}∈U, u^{(t′)}∈U}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)})) if U ∈ U(r, N).

To get such estimates it was natural to impose a bound on

ρ_{α}(u^{(t)}, u^{(t′)}) = [E(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))^{2}]^{1/2} if u^{(t)} ∈ U and u^{(t′)} ∈ U in the definition of the sets U ∈ U(r, N). (See formula (2.11).)

To understand the usefulness of such a bound I recall that the literature contains some bound about the moments of the supremum of Gaussian random variables. If g(1), …, g(r) are jointly Gaussian random variables such that Eg(j) = 0 and Eg(j)^{2} ≤ σ^{2} for all 1 ≤ j ≤ r, then E sup_{1≤j≤r} g(j) ≤ \sqrt{2 log r}σ. Moreover, by

Ledoux’s concentration inequality a good estimate can be given for the high moments of sup_{1≤j≤r} g(j), too. In the Main inequality a similar moment estimate is formulated

for the supremum of the Gaussian random variables Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}). Hence to get a good estimate in this result it is natural to impose a bound on the variances E(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))^{2}, u^{(t)} ∈ U, u^{(t′)} ∈ U. Moreover, we want to get such a bound which does not depend on the parameter r, i.e. on the number of the Gaussian random variables whose supremum is taken. The Main inequality states that this is possible if we impose some additional conditions in the definition of the sets U ∈ U(r, N).

It is simple to prove the Main inequality for very large parameters N whose value may depend on r. But we need this result for the parameter N = 0. The Main inequality will be proved for a general parameter N by means of an appropriate backward induction. This will be carried out with the help of Lemmas 6.1 and 6.2 formulated in the next section. These lemmas enable us to find a good partition Z_{1}, …, Z_{L} of a set

U ∈ U(r, N) which together with the moment estimate E ( sup_{1≤l≤L} Z_{l})^{2R} ≤ ∑_{l=1}^{L} EZ_{l}^{2R}

and a good choice of the parameter R provide an estimate that enables us to carry out an induction procedure leading to the proof of the Main inequality.

Theorem 3 of paper [3] is proved by means of a similar backward induction argument. An essential difference between our proof and that in [3] is that in [3] the expected value and not the high moments of the supremum of a class of Gaussian random variables are bounded. But actually the estimation of the expected value of such suprema is equivalent to the estimation of their high moments because of Ledoux’s concentration inequality. Both here and in [3] the proof is based on a backward induction. In our case this was done by means of appropriate moment estimates while in [3] an estimate was proved about the expected value of the supremum of Gaussian random variables in Lemma 3, and this helped to settle the problem.

There are some additional differences between the formulation of the results in the two works. Thus the inductive hypothesis in the proof of Theorem 3 in [3] depends on two parameters which are changing during the induction. One of them denoted by l is similar to our parameter N, and it is decreasing, the other one r which has the same meaning as in this paper is increasing during the induction steps. Beside this in [3] the quantity α̃(u) = ∑_{1≤j,k≤d−1, j≠k} α̃_{j,k}(u_{j}), u = (u_{1}, …, u_{d−1}), was introduced instead of

the quantities α̃_{j,k}. But the main difference between our proof and that of [3] is that in the latter work the Basic estimate was proved simultaneously with Theorem 3. This implied that in [3] the induction step from l = 1 to l = 0 (and from r to r + 1 with some parameter r) also should have been considered. But the study of this step is missing from this paper. This seems to be an essential gap, because the proof of this step would require some new ideas. Hence I do not consider the proof in [3] complete.

Now I prove the Basic estimate with the help of the Main inequality.

The proof of the Basic estimate. First we show that under the conditions of the Basic estimate U ∈ U(r, 0) for any set U = {(u^{(t)}, 1 ≤ t ≤ r} consisting of r vectors u^{(t)} = (u_{1}^{(t)}, …, u_{d−1}^{(t)}), 1 ≤ t ≤ r, such that 2u_{j}^{(t)} ∈ B^{n_{j}} for all 1 ≤ j ≤ d − 1, 1 ≤ t ≤ r. To show this observe that

ρ_{α}(u^{(t)}, u^{(t′)}) ≤ ρ_{α}(u^{(t)}, 0) + ρ_{α}(u^{(t′)}, 0)

for all 1 ≤ t, t′ ≤ r, where 0 denotes the vector with all coordinates 0, and

ρ_{α}(u^{(t)}, 0) ≤ 2^{−(d−1)} sup_{\begin{matrix}u=(u_{1},...,u_{d−1}): \\ u_{j}∈B^{n_{j}} , 1≤j≤d−1 \end{matrix}} ρ_{α}(u, 0)

= 2^{−(d−1)} sup_{\begin{matrix}u=(u_{1},...,u_{d−1}): \\ u_{j}∈B^{n_{j}} , 1≤j≤d−1 \end{matrix}} [∑_{i_{d}} ( ∑_{i_{1},...,i_{d−1}} a(i_{1}, …, i_{d}) ∏_{j=1}^{d−1} u_{j}(i_{j}))^{2}]^{1/2}

= 2^{−(d−1)} sup_{\begin{matrix}u=(u_{1},...,u_{d}): \\ u_{j}∈B^{n_{j}} , 1≤j≤d \end{matrix}} ∑_{i_{1},...,i_{d}} a(i_{1}, …, i_{d}) ∏_{j=1}^{d} u_{j}(i_{j}) = 2^{−(d−1)}α_{d}

≤ 2^{−(d−1)}M^{−(d−1)/2}

for all 1 ≤ t ≤ r, and a similar estimate holds for ρ_{α}(u^{(t′)}, 0). (We have exploited at this point that the estimate α_{s} ≤ M^{−(s−1)/2} also holds for s = d.) Beside this α_{j,k}(u_{j}^{(t)}) ≤ \frac{1}{2}α_{d−1} ≤ \frac{1}{2}M^{−(d−2)/2}, and clearly u^{(t)} ∈ B^{n_{1}} × ⋯ × B^{n_{d}}, and u^{(t)} − u^{(t′)} ∈ B^{n_{1}} × ⋯ × B^{n_{d}} for all 1 ≤ t, t′ ≤ r. The above relations imply that U ∈ U(r, 0).

It can be proved with the help of the above fact and the Main inequality with the choice N = 0 that

E [  sup_{u∈ \frac{1}{2} B^{n_{1}} ×···× \frac{1}{2} B^{n_{d−1}}} Y_{d}(u)]^{2^{2A_{0}} M} ≤ (C2^{2A_{0}}M^{(d−2)/2})^{2^{A_{0}} M}  (5.8)

with the same number A_{0} which appears in the Main inequality as the threshold index.

To prove this statement let us list the set of vectors u ∈ \frac{1}{2}B^{n_{1}} × ⋯ × \frac{1}{2}B^{n_{d−1}} such that all their coordinates are rational numbers in a sequence u^{(t)}, t = 1, 2, . . .. Let u^{(1)} = (0, …, 0) in this sequence. Let U_{r} = {u^{(t)}, 1 ≤ t ≤ r} be the set consisting of the first r terms of this sequence. Observe that

sup_{u∈B^{n_{1}} ×···×B^{n_{d−1}}} Y_{d}(u) = lim_{r→∞} sup_{u^{(t)}∈U_{r}} Y_{d}(u^{(t)})

Let us apply a weakened form of the Main inequality with N = 0 and A = A_{0} (we may assume that A_{0} ≥ 1) for all above defined sets U_{r}, r = 1, 2, …, where instead of taking the supremum of all differences Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}), 1 ≤ t, t′ ≤ r we take this supremum only for pairs (t, t′) with t′ = 1. In this case Y_{d}(u^{(t′)}) = 0 with probability 1. The series of inequalities obtained in such a way, (where the upper bound does not depend on r) together with the previous identity and the Beppo-Levy theorem imply relation (5.8). This inequality together with the Hölder inequality for p = 2^{2A_{0}−1} yield that

E [  sup_{u∈ \frac{1}{2} B^{n_{1}} ×···× \frac{1}{2} B^{n_{d−1}}} Y_{d}(u)]^{2M} ≤ (C2^{A_{0}}M^{(d−2)/2})^{2M} ≤ C̄^{M}M^{−(d−2)M}  (5.9)

with a universal constant C̄. Relation (2.6) follows from this inequality. To see this it is enough to observe that if the condition u ∈ \frac{1}{2}B^{n_{1}} × ⋯ × \frac{1}{2}B^{n_{d−1}} is replaced by the condition u ∈ B^{n_{1}} ×⋯×B^{n_{d−1}}, then the inequality remains valid if the right-hand side is multiplied by 2^{(d−1)M}, i.e. the constant C̄ is multiplied by 2^{(d−1)} in (5.9).

Paper [3] contained a result in Theorem 3 which can be considered as a generalization of our Basic estimate. Although we do not need it for the sake of completeness I briefly explain how it can be proved with the help of our arguments. First the following statement will be proved.

A generalized form of the Basic estimate. Let the linear form A(v), d ≥ 3, introduced in (1.3) and a positive integer M be such that the quantities α_{s} introduced in (1.7) satisfy the condition (5.6), and let the inequality Δ_{ρ_{α}}(D) ≤ \frac{1}{2}M^{−(d−1)/2} hold for a set D ⊂ B^{n_{1}} × ⋯ × B^{n_{d−1}}, where Δ_{ρ_{α}}(D) = sup_{u∈D, ū∈D} ρ_{α}(u, ū). Then the estimate

E (sup_{u∈D} Y_{d}(u))^{2M} ≤ C^{M}M^{−(d−2)M}  (5.10)

holds for the supremum of the random variables Y_{d}(·) defined in (2.1) with a constant C = C(d) depending only on d.

The proof of the generalized form of the Basic estimate. Let us choose a vector ū ∈ D and define the set D̄ = D̄(ū) = {u: ρ_{α}(u, ū) ≤ M^{−(d−1)/2}}. Then D ⊂ D̄, hence it is enough to prove that version of (5.10) where the set D is replaced by D̄. This estimate can be deduced from the Main inequality with parameter N = 0 similarly to the proof of the Basic estimate only the role of the origin is replaced by the vector ū ∈ D in our consideration. In the proof it is useful to exploit that since the random variables Y_{d}(u) are homogeneous functions of the parameter u. This enables us to restrict our attention to the case when the vector ū = (ū_{1}, …, ū_{d−1}) satisfies the inequality |ū_{j}| ≤ \frac{1}{4} for all 1 ≤ j ≤ d − 1, and |u_{j} − ū_{j}| ≤ \frac{1}{4} for all u = (u_{1}, …, u_{d−1}) ∈ D̄ and 1 ≤ j ≤ d − 1. I omit the details.

The next corollary is equivalent to Theorem 3 of [3].

Corollary of the generalized form of the Basic estimate. For all positive integers M the inequality

E sup_{u∈D} Y_{d}(u) ≤ C(d) (Δ_{ρ_{α}}(D)M^{1/2} + ∑_{s=1}^{d−1} α_{s}(A)M^{−(d−s−1)})

holds with a constant C(d) depending only on the parameter d for any set D ⊂ B^{n_{1}} ×

⋯ × B^{n_{d−1}}, where Δ_{ρ_{α}}(D) = sup_{u∈D, ū∈D} ρ_{α}(u, ū).

Proof of the Corollary. Put

B = B(M) = sup ( sup_{1≤s≤d−1} α_{s}(A)M^{(s−1)/2}, 2Δ_{ρ_{α}}(D)M^{(d−1)/2}) .

Then the conditions of the generalized form of the Basic estimate hold for the linear form B^{−1}A(v) with the parameter M and the set D. Hence relation (5.10) implies that

E (sup_{u∈D} Y_{d}(u))^{2M} ≤ C(d)^{M} (Δ_{ρ_{α}}(D)M^{1/2} + ∑_{s=1}^{d−1} α_{s}(A)M^{−(d−s−1)})^{2M} .

This relation together with the Hölder inequality imply the corollary.

6. Some results about the existence of good partitions.

The Main inequality will be proved with the help of Lemmas 6.1 and 6.2 formulated in this section. They give a good partition of a set U ∈ U(r, N). We would like to find such a partition U_{1}, …, U_{L} of a set U ∈ U(r, N) with a relatively not too large parameter L for which the diameters Δ_{ρ_{α}}(U_{l}) = sup_{u∈U_{l},ū∈U_{l}} ρ_{α}(u, ū) of the sets U_{l} are

small, and the sets U_{l} satisfy some additional useful properties, too. But we can prove only a weaker result. We can partition a set U ∈ U(r, N) only to the ‘shifts’ of sets with small diameters, i.e. to sets u_{l} + U_{l}, 1 ≤ l ≤ L, such that u_{l} ∈ U and the diameters Δ_{ρ_{α}}(U_{l}) are small. (Observe that the metric ρ_{α} is not translation invariant.) The precise formulation of this result will be given in Lemma 6.1. This lemma is not sufficient for our purposes. Hence we shall prove a strengthened form of it in Lemma 6.2. It states the existence of a partition of a set U ∈ U(r, N) with the properties of Lemma 6.1 and some additional properties useful for us. Beside this the cardinality of a partition appearing in Lemma 6.2 has a bound similar to the case in Lemma 6.1.

Lemmas 6.1 and 6.2 will be proved with the help of the corollary of Proposition 4.2. But to apply this result we need some bound on the quantities W_{I}^{x}(α, 4t) appearing in it. To have such bounds we shall formulate and prove Lemma 6.3 in this section. Lemmas 6.1 and 6.2 can be considered as a version of Lemma 8 and Lemma 6.3 as a version of Lemmas 5 and 6 in [3].

To formulate the above results some additional notations will be introduced. We define with the help of a vector u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and a set I ⊂ {1, …, d − 1} an operator depending on this vector u and set I which is a special case of the class of operators defined in formula (1.4). We also introduce some quantities corresponding to this operator which are the analogs of the quantities α_{s}, α̃_{j,k}, ρ_{α} defined earlier with the help of the operator A(v) given in (1.3).

Fix a set I = {j_{1}, …, j_{s}} ⊂ {1, …, d − 1} with 1 ≤ s ≤ d − 2 elements and a vector u = (u_{1}, …, u_{d−1}) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}}. Let us define with their help the numbers

b_{u}^{I}(i_{j}, j ∈ {1, …, d} \ I) = M^{|I|/2} ∑_{(i_{j}, j∈I)} a(i_{1}, …, i_{d}) ∏_{j∈I} u_{j}(i_{j})  (6.1)

depending on the vectors (i_{j}, j ∈ {1 …, d} \ I) and the linear functional

B_{u}^{I}(v) = ∑_{(i_{j}, j∈{1,...,d)\I)} b_{u}^{I}(i_{j}, j ∈ {1, …, d} \ I)v(i_{j}, j ∈ {1, …, d} \ I)  (6.2)

acting on the space of functions v = v(i_{j_{1}}, …, i_{j_{p}}) ∈ R^{n_{j_{1}}} ⊗ ⋯ ⊗ R^{n_{jp}}, with the set of indices {j_{1}, …, j_{p}} = {1, …, d} \ I.

This operator B_{u}^{I}(v) is a special case of the operators B_{K}(v) defined in formula (1.4) when K = {1, …, d} \ I, and coefficients b_{K}(·) are the numbers b_{u}^{I}(·) defined in (6.1). (In the definition of the coefficients b_{u}^{I}(i_{j}, j ∈ {1, …, d} \ I) in (6.1) a multiplying factor M^{|I|/2} was inserted. I applied such a norming factor, because it simplifies the subsequent calculations.)

We can define the quantities V (P, B_{u}^{I}) for all partitions P of the set K = {1, …, d}\ I by formula (1.6) with the choice B_{K}(v) = B_{u}^{I}(v). Let us also introduce, similarly to α_{s} defined in (1.7), the quantity

α_{u,s}(I) = sup_{P: |P |=s} V (P, B_{u}^{I}),  (6.3)

where all partitions P of the set {1, …, d} \ I with cardinality s are taking part in the supremum. We also introduce the numbers

α̃_{k}^{I}(u) = V (P_{I,k}, B_{u}^{I}) for all k ∈ {1, …, d − 1} \ I  (6.4)

with the help of formula (1.6), where the operator B_{u}^{I}(v) defined in (6.2) plays the role of B_{K}(v), and the partition P_{I,k} of the set {1, …, d}\I is defined as P_{I,k} = {{k, d}, {l}, l ∈ {1, …, d − 1} \ (I ∪ {k})}.

We shall also work with a quantity ρ_{α_{u}^{I}}(v, v̄) defined for all pairs (v, v̄), v ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and v̄ ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} with the help of a vector u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and set I ⊂ {1, …, d−1}, 1 ≤ |I| ≤ d−2, similarly to the term ρ_{α} introduced in (2.11). First we define a version of it.

\begin{aligned}ρ̄_{α_{u}^{I}}(v, v̄) = ( & ∑_{i_{d}}[  ∑_{(i_{j}, j∈\{1,...,d−1\}\I)} b_{u}^{I}(i_{j}, j ∈ \{1, …, d\} \ I) \\ & (  ∏_{j∈\{1,...,d−1\}\I} v(i_{j}) − ∏_{j∈\{1,...,d−1\}\I} v̄(i_{j}))]^{2})^{1/2} \end{aligned}  (6.5)

for pairs of vectors v = (v_{j_{1}}, …, v_{j_{p}}) ∈ R^{n_{j_{1}}} × ⋯ × R^{n_{jp}} and v̄ = (v̄_{j_{1}}, …, v̄_{j_{p}}) ∈ R^{n_{j_{1}}} × ⋯ × R^{n_{jp}}, where {j_{1}, …, j_{p}} = {1, …, d − 1} \ I. Observe that ρ̄_{α_{u}^{I}} is the pseudometric induced by the pseudonorm

\begin{aligned}α_{u}^{I}(v) & = α_{u}^{I}(v(i_{j}, j ∈ \{1, …, d − 1\} \ I)) \\ & = (∑_{i_{d}}[  ∑_{(i_{j}, j∈\{1,...,d−1\}\I)} b_{u}^{I}(i_{j}, j ∈ \{1, …, d\} \ I) \\ & v(i_{j}, j ∈ \{1, …, d − 1\} \ I)]^{2})^{1/2} \end{aligned}  (6.6)

on the tensor product R^{n_{j_{1}}} ⊗ ⋯ ⊗ R^{n_{jp}}, where {j_{1}, …, j_{p}} = {1, …, d − 1} \ I.

We can define the metric ρ_{α_{u}^{I}} in the space R^{n_{1}} × ⋯ × R^{n_{d−1}} with the help of the metric ρ̄_{α_{u}^{I}} defined in (6.5). To do this we introduce the following notation. Given a vector v = (v_{1}, …, v_{d−1}) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and a set I ⊂ {1, …, d − 1} let v_{I^{c}} denote the vector we obtain by omitting the coordinates of the vector v belonging to the set I, i.e. let v_{I^{c}} ∈ R^{n_{j_{1}}} × ⋯ × R^{n_{jp}} such that v_{I^{c}} = (v_{j}, j ∈ {1, …, d − 1} \ I). Given two vectors v = (v_{1}, …, v_{d−1}) ∈ R^{n_{1}} ×⋯×R^{n_{d−1}} and v̄ = (v̄_{1}, …, v̄_{d−1}) ∈ R^{n_{1}} ×⋯×R^{n_{d−1}} put

ρ_{α_{u}^{I}}(v, v̄) = ρ̄_{α_{u}^{I}}(v_{I^{c}}, v̄_{I^{c}}).  (6.7)

Now I formulate Lemma 6.1 and its strengthened version Lemma 6.2.

Lemma 6.1. If an operator A of order d ≥ 3 satisfies relation (5.6), then each set U ∈ U(r, N) = U_{A,M,d}(r, N) has a partition u^{(1)} + U_{1}, u^{(2)} + U_{2}, …, u^{(L)} + U_{L} with L ≤ 2^{C(d)M2^{2N}} elements such that U_{l} ∈ U(r, N + 2) and u^{(l)} ∈ U for all 1 ≤ l ≤ L. The number C(d) depends only on the order d of the operator A.

Lemma 6.2. If an operator A of order d ≥ 3 satisfies relation (5.6), then each set U ∈ U(r, N) has a partition u^{(l)}+U_{l}, l = 1 …, L, with L ≤ 2^{C(d)M2^{2N}} elements such that u^{(l)} ∈ U, U_{l} ∈ U(r, N + 2), 1 ≤ l ≤ L, and it also has the following additional property. The inequality ρ_{α_{u^{(l)}}^{I}} (u, ū) ≤ 2^{−2N}M^{−(d−|I|−1)/2} holds for all sets I ⊂ {1, …, d − 1},

1 ≤ |I| < d − 2, and pairs of elements u ∈ U_{l} and ū ∈ U_{l}, 1 ≤ l ≤ L. The vector u^{(l)} in this inequality is the same vector which appears in the definition of the element u^{(l)} + U_{l} of the partition of U. The quantity ρ_{α_{u}^{I}}(·, ·) was defined in (6.5) and (6.7).

Lemmas 6.1 and 6.2 will be proved with the help of the following Lemma 6.3.

Lemma 6.3. Let a functional A(v) of order d ≥ 3 defined in (1.3) satisfy condition (5.6). Then for any u = (u_{1}, …, u_{d−1}) ∈ B^{n_{1}} ×⋯×B^{n_{d−1}} the quantities W_{I}^{u}(α, t), I ∈ {1, …, d − 1}, I ≠ ∅, defined in (4.2) with the pseudonorm α introduced in (2.12) satisfy the following inequalities.

W_{I}^{u}(α, t) ≤ \frac{t^{|I|}}{M^{(d−|I|−1)/2}} if 2 ≤ |I| ≤ d − 1.  (6.8)

For a set I = {k} containing one element

W_{{k}}^{u}(α, t) ≤ t min_{1≤j≤d−1, j≠k} α̃_{j,k}(u_{j}),  (6.9)

where α̃_{j,k}(u_{j}) was defined in (5.3). Beside this,

Eα̃_{j,k}(G_{j}) ≤ \frac{C(d)}{M^{(d−3)/2}} for all 1 ≤ j, k ≤ d − 1, j ≠ k,  (6.10)

where C(d) depends only on d, and G_{j} is a standard normal vector of dimension n_{j}.

The proof of Lemma 6.3. For any set I ⊂ {1, …, d−1}, I ≠ ∅ and u ∈ B^{n_{1}} ×⋯×B^{n_{d−1}}

W_{I}^{u}(α, 1) = E ([∑_{i_{d}} ( ∑_{i_{1},...,i_{d−1}} a(i_{1}, …, i_{d}) ∏_{j∈{1,...,d−1}\I} u_{j}(i_{j}) ∏_{j∈I} g_{j}(i_{j}))^{2}])^{1/2}

≤ (E [∑_{i_{d}} ( ∑_{i_{1},...,i_{d−1}} a(i_{1}, …, i_{d}) ∏_{j∈{1,...,d−1}\I} u_{j}(i_{j}) ∏_{j∈I} g_{j}(i_{j}))^{2}])^{1/2}

= [ ∑_{(i_{p}, p∈I∪{d})} (  ∑_{(i_{j}, j∈{1,...,d−1}\I)} a(i_{1}, …, i_{d}) ∏_{j∈{1,...,d−1}\I} u_{j}(i_{j}))^{2}]^{1/2}

= sup_{\begin{matrix}v(i_{p}, p∈I∪\{d\}): \\ ∑ v^{2}(i_{p}, p∈I∪\{d\})≤1 \end{matrix}} ∑_{i_{1},...,i_{d}} a(i_{1}, …, i_{d}) ∏_{j∈\{1,...,d−1\}\I} u_{j}(i_{j})v(i_{p}, p ∈ I ∪ \{d\})

≤ V (P_{I}, A),  (6.11)

where P_{I} is the partition P_{I} = {I ∪ {d}, {j}, 1 ≤ j ≤ d − 1, j ∉ I} of the set {1, …, d}, and V (P, A) is defined in (1.6).

Since the partition P_{I} has d − |I| elements this inequality together with relation (5.6) imply that for |I| ≥ 2

W_{I}^{u}(α, t) = t^{|I|}W_{I}^{u}(α, 1) ≤ t^{|I|}α_{|P_{I}|}(A) ≤ \frac{t^{|I|}}{M^{(d−|I|−1)/2}} ,

i.e. (6.8) holds. In the case I = {k} we get from the last but one bound in (6.11), the representation of α̃_{j,k}(u_{j}) in formula (5.4) and the choice of an arbitrary point j ∈ {1, …, d−1}\{k} that W_{I}^{u}(α, 1) ≤ α̃_{j,k}(u_{j}), and this relation implies formula (6.9).

Inequality (6.10) can be deduced from inequality (2.6) in the Basic estimate with parameter d−1 if we write up the expression α̃_{j,k}(G_{j}) in the form (5.4), (by replacing the vector u_{j} by G_{j} in it), consider it as an expression of the form (2.1) with d − 1 variables by taking the pair (k, d) as one variable. Let us observe that relation (5.6) implies relation (1.10) with parameter d−1 in this case, hence we may apply the Basic estimate. Let us apply a reindexation of the arguments by which the j-th variable turns to the d−1th coordinate. The Basic estimate remains valid after such a reindexation. Since in the proof of Lemma 6.3 for parameter d we may assume that the Basic estimate holds for d−1 we get inequality (6.10) from the Basic estimate and the estimate EZ_{d} ≤ (EZ_{d}^{2M})^{1/2M} which is a consequence of Hölder’s inequality.

7. The proof of Lemmas 6.1 and 6.2 about the existence of good partitions.

In this section Lemmas 6.1 and 6.2 will be proved with the help of the corollary of Proposition 4.2 and Lemma 6.3.

The proof of Lemma 6.1. If relation (5.6) holds, then relation (6.10) in Lemma 6.3 implies the inequality Eα̃_{j,k}(G_{j}) ≤ CM^{−(d−3)/2} for all 1 ≤ j, k ≤ d − 1, j ≠ k. Hence Proposition 4.1 yields the estimate μ_{n_{j},t}(y: y ∈ R^{n_{j}}, α̃_{j,k}(x − y) ≤ CtM^{−(d−3}/2) ≥ e^{−C′/t^{2}M^{(d−3)}} for all numbers t > 0, pairs (j, k), 1 ≤ j, k ≤ d − 1, j ≠ k, and x ∈ B^{n_{j}}, where μ_{n_{j},t} denotes the distribution of tG_{j} if G_{j} is a standard normal vector of dimension n_{j}. Hence the corollary of Proposition 4.2 applied for the metric ρ_{α}(x, y) = α̃_{j,k}(x − y) in the space R^{n_{j}} with the choice D = B^{n_{j}}, t = C2^{−N}M^{−1/2} and u = 2^{−(N+4)}M^{−(d−2)/2} yields the following result.

For all pairs (j, k), 1 ≤ j, k ≤ d − 1, j ≠ k, the unit ball B^{n_{j}} ⊂ R^{n_{j}} has a partition Û_{1}^{(j,k)}, …, Û_{L(j,k)}^{(j,k)} with L(j, k) ≤ e^{C/t^{2}} ≤ 2^{C2^{2N} M} elements such that α̃_{j,k}(y − x) ≤

2^{−(N+2)}M^{−(d−2)/2} if x ∈ Û_{l}^{(j,k)} and y ∈ Û_{l}^{(j,k)} with the same index l. Hence any set U ⊂ B^{n_{1}} × ⋯ × B^{n_{d−1}}, in particular any set U ∈ U(r, N) has a partition U_{1}^{(j,k)}, …, U_{L(j,k)}^{(j,k)}

with L(j, k) ≤ 2^{C2^{2N} M} elements such that α̃_{j,k}(x_{j} − y_{j}) ≤ 2^{−(N+2)}M^{−(d−2)/2} if x = (x_{1}, …, x_{d−1}) ∈ U_{l}^{(j,k)} and y = (y_{1}, …, y_{d−1}) ∈ U_{l}^{(j,k)} with the same index 1 ≤ l ≤ L(j, k). Indeed, the sets U_{l}^{(j,k)} = {y = (y_{1}, …, y_{d−1}): y ∈ U, y_{j} ∈ Û_{l}^{(j,k)}}, 1 ≤ l ≤ L(j, k), provide such a partition of U.

The existence of such partitions for all pairs (j, k), 1 ≤ j, k ≤ d − 1, j ≠ k, implies that each set U ∈ U(r, N) has a partition of the form u^{(1)} + Ū_{1}, u^{(2)} + Ū_{2}, …, u^{L} + Ū_{L} with L ≤ 2^{C(d)M2^{2N}} elements such that u^{(l)} ∈ U, and α̃_{j,k}(u_{j}) ≤ 2^{−(N+2)}M^{−(d−2)/2} if u = (u_{1}, …, u_{d−1}) ∈ Ū_{l} with some 1 ≤ l ≤ L for all 1 ≤ j, k ≤ d − 1, j ≠ k.

To show this let us consider for all pairs (j, k), 1 ≤ j, k ≤ d − 1, j ≠ k, a partition U_{1}^{(j,k)}, …, U_{L(j,k)}^{(j,k)} of the set U with L(j, k) ≤ 2^{C2^{2N} M} elements such that α̃_{j,k}(x_{j} −

y_{j}) ≤ 2t if x = (x_{1}, …, x_{d−1}) ∈ U_{l}^{(j,k)} and y = (y_{1}, …, y_{d−1}) ∈ U_{l}^{(j,k)} with the same index l = l(j, k). Take all intersections of the form ⋂_{(j,k): 1≤j,k≤d−1,j≠k} U_{l(j,k)}^{(j,k)}, i.e. take

all possible intersections which contain exactly one element from each of the above partitions indexed by the pairs (j, k). By reindexing the sets obtained in such a way we get a partition Ũ_{1}, …, Ũ_{L} of the set U with L ≤ 2^{C2^{2N} M} elements such that for all pairs u = (u_{1}, …, u_{d−1}) ∈ Ũ_{l} and ū = (ū_{1}, …, ū_{d−1}) ∈ Ũ_{l} with the same index l and 1 ≤ j, k ≤ d − 1, j ≠ k, α̃_{j,k}(u_{j} − ū_{j}) ≤ 2^{−(N+2)}M^{−(d−2)/2}. Then choosing an arbitrary element u^{(l)} ∈ Ũ_{l} and writing Ũ_{l} = u^{(l)} + Ū_{l} with Ū_{l} = {u − u^{(l)}: u ∈ Ũ_{l}} we get a partition with the desired property.

It can be shown with the help of the corollary of Proposition 4.2 that each set Ū_{l}, taking part in the above constructed partition u^{(l)}+Ū_{l}, 1 ≤ l ≤ L, of the set U has a partition U_{l,1} …, U_{l,L_{l}} with L_{l} ≤ 2^{C2^{2N} M} elements such thatρ_{α}(u, ū) ≤ 2^{−2(N+2)}M^{−(d−1)/2} if u ∈ U_{l,p} and ū ∈ U_{l,p} with the same parameters l and p. Indeed, let us choose t = c2^{−N}M^{−1/2} with a sufficiently small constant 1 ≥ c > 0. Observe that with the choice of such a number t and a vector u ∈ Ū_{l} with some index 1 ≤ l ≤ L we can write by (6.8)

W_{I}^{u}(α, t) ≤ \frac{t^{|I|}}{M^{(d−|I|−1)/2}} ≤ c^{2}2^{−2N}M^{−(d−1)/2}

for all sets I ⊂ {1, …, d − 1} such that |I| ≥ 2. For a set I = {k}, 1 ≤ k ≤ d − 1, containing one element we have

W_{{k}}^{u}(α, t) ≤ t min_{1≤j≤d−1, j≠k} α̃_{j,k}(u_{j}) ≤ c2^{−2N}M^{−(d−1)/2}

by relations (6.9) and α̃_{j,k}(u_{j}) ≤ 2^{−(N+2)}M^{−(d−2)/2} if u = (u_{1}, …, u_{d−1}) ∈ Ū_{l}. Hence

∑_{I: I⊂{1,...,d−1}, I≠∅} W_{I}^{u}(α, 4t) ≤ 2^{−2(N+3)}M^{−(d−1)/2}

for a vector u ∈ Ū_{l} if the parameter c > 0 is chosen sufficiently small. Then an application of the corollary of Proposition 4.2 for each set Ū_{l}, 1 ≤ l ≤ L with the metric ρ_{α} and the choice t = c2^{−N}M^{−1/2} and u = 2^{−2(N+3)}M^{−(d−1)/2} shows that there exists a partition U_{l,p}, 1 ≤ p ≤ L_{l}, of Ū_{l} of cardinality L_{l} ≤ 2^{C_{1}/t^{2}} ≤ 2^{CM2^{2N}} with the desired property.

Put u^{(l,p)} = u^{(l)} for all 1 ≤ l ≤ L and 1 ≤ p ≤ L_{l}, and consider all sets u^{(l,p)} + U_{l,p}, 1 ≤ l ≤ L, 1 ≤ p ≤ L_{l}. A reindexation of these sets provides a partition of the set U ∈ U(r, N) that satisfies Lemma 6.1. Indeed, these sets provide a partition of the set U with L ≤ 2^{CM2^{2N}} elements. Beside this, u^{(l,p)} ∈ U for all indices l and p. We still have to check that U_{l,p} ∈ U(r, N +2) for all pairs of indices l and p. The elements of the sets U_{l,p} satisfy the desired inequalities for α̃_{j,k} and ρ_{α}, and the sets U_{l,p} have at most r elements. To check that the sets U_{l,p} satisfy the remaining properties of the elements of the class U(r, N + 2) observe that for a point u ∈ U_{l,p} u = ũ − u^{(l)} with ũ ∈ Ũ_{l,p} ⊂ U and u^{(l)} ∈ U, hence u ∈ B^{n_{1}} × ⋯ × B^{n_{d−1}}. The analogous statement also holds for a difference u − u′ with u ∈ U_{l,p} and u′ ∈ U_{l,p}, since such a difference can be written as the difference of two vectors from the set Ũ_{l} ⊂ U.

The proof of Lemma 6.2. The main step of the proof is the verification of the following statement formulated in relation (7.1).

Take a partition u^{(l)} +U_{l}, 1 ≤ l ≤ L, of a set U ∈ U(r, N) that satisfies Lemma 6.1, and fix one of the vectors u^{(l)} in this partition together with a set I ⊂ {1, …, d − 1}, 1 ≤ |I| ≤ d − 2. There is a partition V_{1} = V_{1}(l, I), …, V_{L} = V_{L(l,I)}(l, I) with L(l, I) ≤ 2^{C2^{2N} M} elements of the product of unit balls B^{n_{j_{1}}} × ⋯ × B^{n_{jr}} with indices {j_{1}, …, j_{r}} = {1, …, d − 1} \ I such that

ρ̄_{α_{u^{(l)}}^{I}} (v, v̄) ≤ 2^{−2N}M^{−(d−|I|−1)/2} if v ∈ V_{p}(l, I) and v̄ ∈ V_{p}(l, I)

with the same index p,

(7.1)

i.e. this inequality holds if v and v̄ are contained in the same element of the partition V_{p}(l, I), 1 ≤ p ≤ L(l, I), of the set B^{n_{j_{1}}} × ⋯ × B^{n_{jr}}. The metric ρ̄_{α_{u}^{I}}(v, v̄) (with a general vector u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}}) was defined in formula (6.5).

First the following inequalities will be verified. For all sets I, I ⊂ {1, …, d − 1}, 1 ≤ |I| ≤ d − 2

α_{u^{(l)},s}(I) ≤ M^{−(s−1)/2} for all 1 ≤ s ≤ d − |I| − 1  (7.2)

and

α̃_{k}^{I}(u^{(l)}) ≤ 2^{−N}M^{−(d−|I|−2)/2} for all k ∈ {1, …, d − 1} \ I,  (7.3)

where α_{u,s}(I) was defined in (6.3) and α̃_{k}^{I}(u) in (6.4) (for a general vector u).

To check (7.2) let us compare a partition P of {1, …, d} \ I of cardinality |P | = s, 1 ≤ s ≤ d − |I| − 1, with the partition P̄ of the set {1, …, d} we get by attaching all one point sets of I to the elements of the partition P. Then |P̄| = s + |I|, hence V (P̄, A) ≤ α_{s+|I|}(A) ≤ M^{−(s+|I|−1)/2} by relation (5.6) and V (P, B_{u^{(l)}}^{I}) ≤ M^{|I|/2}V (P̄, A) ≤ M^{−(s−1)/2}. Since this relation holds for all partitions P such that |P | = s this implies (7.2).

Beside this the relation u^{(l)} ∈ U with an U ∈ U(r, N) implies that α̃_{j,k}(u_{j}^{(l)}) ≤ 2^{−N}M^{−(d−2)/2}, hence α̃_{k}^{I}(u^{(l)}) ≤ M^{|I|/2}α̃_{j,k}(u_{j}^{(l)}) ≤ 2^{−N}M^{−(d−|I|−2)/2} for all j ∈ I and k ∈ {1, …, d − 1} \ I. Thus relation (7.3) also holds.

First we prove the existence of a partition with less than 2^{C2^{2N} M} elements that satisfies (7.1) only in the case |I| ≤ d−3. This will be done with the help of the corollary of Proposition 4.2 when it is applied to the metric ρ̄_{α_{u^{(l)}}^{I}} and the norm α_{u^{(l)}}^{I} inducing

it. These quantities were introduced in (6.5) and (6.6). In the proof we need good estimates on the terms W_{K}^{u}(α_{u^{(l)}}^{I}, t) defined in (4.2) for all sets K ⊂ {1, …, d − 1} \ I, K ≠ ∅ and u ∈ B^{n_{j_{1}}} × ⋯ × B^{n_{js}} with a number t chosen as t = c2^{−N}M^{−1/2} with a sufficiently small constant 1 ≥ c > 0. This quantity will be bounded by means of the estimates (7.2), (7.3) and Lemma 6.3. More precisely an equivalent version of Lemma 6.3 will be applied where B_{u^{(l)}}^{I} (defined in (6.2)) is chosen as the operator A, and as a consequence α_{u^{(l)},s}(I) defined in (6.3) plays the role of the term α_{s} = α_{s}(A). This term must satisfy relation (5.6) to have the right to apply Lemma 6.3. (Actually the variables of the operator B_{u^{(l)}}^{I} have to be reindexed if we want to apply Lemma 6.3 in its original form.) The operator B_{u^{(l)}}^{I} acts on the functions on {1, …, d} \ I, on a set of d − |I| elements, and by relation (7.2) α_{u^{(l)},s}(I) ≤ M^{−(s−1)/2} if 1 ≤ s ≤ d−|I|−1. This means that formula (5.6) holds for the operator we get by an appropriate reindexation the indices {1, …, d} \ I of the arguments of B_{u^{(l)}}^{I} to the set 1, …, d − |I|. An appropriate reindexation is obtained if the elements of the set {1, …, d} \ I are listed in a monotone increasing order, and the j-th element of this sequence gets the index j. Such a reindexation of the indices yields a version of Lemma 6.3 that enables us to estimate the terms W_{K}^{u}(α_{u^{(l)}}^{I}, t). (Originally we get an estimate for a version of W_{K}^{u}(α_{u^{(l)}}^{I}, t) with reindexed parameters by means of a version of B_{u^{(l)}}^{I} with reindexed parameters.)

In the application of Lemma 6.3 we still have to understand what α̃_{j,k}(u_{j}) means in formula (6.9) if B_{u^{(l)}}^{I} plays the role of the operator A.

By formula (6.8) in Lemma 6.3 we get that

W_{K}^{u}(α_{u^{(l)}}^{I}, t) ≤ \frac{t^{|K|}}{M^{(d−|I|−|K|−1)/2}} ≤ c^{2}2^{−2N}M^{−(d−|I|−1)/2} if 2 ≤ |K| ≤ d − |I| − 1.

I claim that relations (6.9) and (7.3) imply that

W_{{k}}^{u}(α_{u^{(l)}}^{I}, t) ≤ tα̃_{k}^{I}(u^{(l)}) ≤ c2^{−2N}M^{−(d−|I|−1)/2}

for a one point set {k} ∈ {1, …, d − 1} \ I. We get this bound from (7.3) if we show that α̃_{j,k}(u_{j}) ≤ α_{k}^{I}(u^{(l)}) for any j ∈ {1, …, d − 1} \ I, j ≠ k, with the function α̃_{j,k}(u_{j}) corresponding to the operator B_{u^{(l)}}^{I} if u_{j} ∈ B^{n_{j}}.

This inequality can be seen by giving a good representation of α̃_{j,k}(u_{j}) when it corresponds to B_{u^{(l)}}^{I} instead of A together with a similar representation of α̃_{k}^{I}(u^{(l)}). An adaptation of formula (5.4) will be applied to this case. The main difference between formula (5.4) and the representation of α̃_{j,k}(u_{j}) given below is that in the new formula we have the fixed functions u_{s}^{(l)}(·) in the coordinates s ∈ I. In this case we have

α̃_{j,k}(u_{j}) = sup_{v_{p}(·), p∈{1,...,d−1}\(I∪{j,k}, v_{k,d}(·,·)} ∑_{i_{1},...,i_{d}} a(i_{1}, …, i_{d})u_{j}(i_{j})v_{k,d}(i_{k}, i_{d})

∏_{s∈I} u_{s}^{(l)}(i_{s}) ∏_{p∈{1,...,d−1}\(I∪{j,k})} v_{p}(i_{p})

for a vector u_{j} ∈ R^{n_{j}}, where the supremum is taken for such vectors v_{p}(·) depending on the coordinate i_{p}, p ∈ {1, …, d − 1} \ (I ∪ {j, k}), for which ∑_{i_{s}} v_{p}^{2}(i_{p}) ≤ 1 and a function

v_{k,d}(·, ·), depending on the coordinates i_{k} and i_{d} such that ∑_{i_{k},i_{d}} v^{2}(i_{k}, i_{d}) ≤ 1. The

expression α̃_{k}^{I}(u^{(l)}) has a similar representation, only in its definition we have to take supremum also for all vectors v_{j}(·) ∈ B^{n_{j}} in its j-th coordinate instead of fixing a vector u_{j} ∈ B^{n_{j}} as it was done in the definition of α̃_{j,k}(u_{j}), u_{j} ∈ B^{n_{j}}. These observations imply the desired inequality α̃_{j,k}(u_{j}) ≤ α_{k}^{I}(u^{(l)}).

The above inequalities imply that

∑_{J: J⊂{1,...,d−1}\I, J≠∅} W_{J}^{u}(α_{u^{(l)}}^{I}, 4t) ≤ 2^{−2(N−1)}M^{−(d−|I|−1)/2}

for all u ∈ B^{n_{j_{1}}} × ⋯ × B^{n_{js}} if the constant c > 0 in the choice t = c2^{−N}M^{−1/2} is sufficiently small. Hence relation (7.1) follows from the corollary of Proposition 4.2 applied for the metric ρ̄_{α_{u^{(l)}}^{I}} induced by the norm α_{u^{l)}}^{I} with the choice D = B^{n_{j_{1}}} ×⋯×B^{n_{jr}} and

t = c2^{−N}M^{−1/2} with a sufficiently small number c > 0 and u = 2^{−2(N−1)}M^{−(d−|I|−1)/2}.

In the case |I| = d − 2 we can write I = {1, …, d − 1} \ {k} with an appropriate k ∈ {1, …, d − 1}. The inequality α̃_{j,k}(u^{(l)}) ≤ 2^{−N}M^{(d−2)/2} with an arbitrary index j ∈ I implies in this case that

∑_{i_{k},i_{d}} b_{u^{(l)}}^{I}(i_{k}, i_{d})v(i_{k}, i_{d}) ≤ M^{|I|/2}2^{−N}M^{−(d−2)/2} ≤ 2^{−N} if ∑_{i_{k},i_{d}} v^{2}(i_{k}, i_{d}) ≤ 1,

or in an equivalent form

∑_{i_{k},i_{d}} b_{u^{(l)}}^{I}(i_{k}, i_{d})^{2} ≤ 2^{−2N},  (7.4)

where I = {1, …, d − 1} \ {k}, and the numbers b_{u^{(l)}}^{I}(i_{k}, i_{d}) are defined in (6.1). Let us also define the pseudonorm

β_{u^{(l)}}^{I}(v) = [∑_{i_{d}} (∑_{i_{k}} b_{u^{(l)}}^{I}(i_{k}, i_{d})v(i_{k}))^{2}]^{1/2}

of the vectors v = (v(1), …, v(n_{k})) ∈ R^{n_{k}}.

The pseudometric ρ̄_{α_{u^{(l)}}^{I}} defined in (6.5) agrees in this case with the metric induced

by the pseudonorm β_{u^{(l)}}^{I}. Hence in this case the existence of a partition V_{1}, …, V_{L} of B^{n_{k}} with L ≤ 2^{C2^{2N} M} elements and the property ρ̄_{α_{u^{(l)}}^{I}} (v, v̄) ≤ 2^{−2N}M^{−1/2}, if v, v̄ ∈ V_{l}

with some 1 ≤ l ≤ L, i.e. relation (7.1) can be proved with the help of the corollary of Proposition 4.2 and the following estimate on the pseudonorm β_{u^{(l)}}^{I}.

By the Schwarz inequality and formula (7.4)

\begin{aligned}Eβ_{u^{(l)}}^{I}(G_{k}) & ≤ [∑_{i_{d}} E (∑_{i_{k}} b_{u^{(l)}}^{I}(i_{k}, i_{d})g_{k}(i_{k}))^{2}]^{1/2} \\ & = [∑_{i_{k},i_{d}} b_{u^{(l)}}^{I}(i_{k}, i_{d})^{2}]^{1/2} ≤ 2^{−N} \end{aligned}  (7.5)

for a standard normal random vector G_{k} = (g_{k}(1), …, g_{k}(n_{k})) of dimension n_{k}. Because of relation (7.5) an application of the corollary of Proposition 4.2 for the operator β_{u^{(l)}}^{I} with 4t = 2^{−(N+2)}M^{−1/2} and u = 2^{−2(N+1)}M^{−1/2} shows the existence of a partition V_{1}, …, V_{L} of B^{n_{k}} with L ≤ 2^{C_{1}/t^{2}} ≤ 2^{C2^{2N} M} elements such that ρ̄_{α_{u^{(l)}}^{I}} (v, v̄) = β_{u^{(l)}}^{I}(v −

v̄) ≤ 2^{−2(N+1)}M^{−1/2} if v ∈ V_{l}, v̄ ∈ V_{l} with some 1 ≤ l ≤ L as we claimed.

Let us fix some u^{(l)} appearing in the partition u^{(l)}+U_{l}, 1 ≤ l ≤ L of the set U we are considering. It follows from relation (7.1) that there exists a partition V_{1}(l), …, V_{L_{l}}(l) of B^{n_{1}} × ⋯ × B^{n_{d−1}} with L_{l} ≤ 2^{C2^{2N} M} elements such that

ρ_{α_{u^{(l)}}^{I}} (v, v̄) ≤ 2^{−2N}M^{−(d−|I|−1)/2} if v ∈ V_{p}(l) and v̄ ∈ V_{p}(l) with the same
index p for all I ⊂ {1, …, d − 1} such that 1 ≤ |I| ≤ d − 2.

(7.6)

Indeed, it follows from (7.1) and the definition of ρ_{α_{u^{(l)}}^{I}} in (6.5) and (6.7) that

for all sets I ⊂ {1, …, d − 1}, 1 ≤ |I| ≤ d − 2, there is a partition V_{1}(l, I), …, V_{L(l,I)}(l, I) of B^{n_{1}} × ⋯ × B^{n_{d−1}} depending on l and I with L(l, I) ≤ 2^{C2^{2N} M} elements such that ρ_{α_{u^{(l)}}^{I}} (v, v̄) ≤ 2^{−2N}M^{−(d−|I|−1)/2} if v ∈ V_{p}(l, L) and v̄ ∈ V_{p}(l, L with the

same index p. Then taking all possible intersections ⋂_{I: I∈{1,...,d−1}, 1≤|I|≤d−2} V_{p(I)}(I, l)

that contain exactly one element from each above introduced partitions depending on the sets I ⊂ {1, …, d − 1}, 1 ≤ |I| ≤ d − 2, we get a partition of B^{n_{1}} × ⋯ × B^{n_{d−1}} that satisfies (7.6). Let us observe that the number of elements of this partition also can be bounded from above by 2^{C2^{2N} M} with some constant C > 0.

Let us choose a partition V_{1}(l), …, V_{L_{l}}(l) of B^{n_{1}} × ⋯ × B^{n_{d−1}} satisfying relation (7.6) for all vectors u^{(l)} taking part in a partition u^{(l)} + U_{l}, 1 ≤ l ≤ L satisfying Lemma 6.1. Then the ensemble of sets u^{(l,p)} +(V_{p}(l)∩U_{l}), 1 ≤ p ≤ L(l), 1 ≤ l ≤ L, with u^{(l,p)} = u^{(l)} constitutes a partition of the set U which, after an appropriate reindexation, satisfies Lemma 6.2.

8. The proof of the Main inequality.

In this section I prove the Main inequality with the help of Lemma 6.2.

The proof of the Main inequality. First it will be shown that relation (5.7) holds with an appropriate constant C = C(d) in it if N ≥ N_{0} with a sufficiently large threshold index N_{0} = N_{0}(r). To this end let us observe that

E(Y_{d}(u) − Y_{d}(u′))^{2} = ρ_{α}(u, u′)^{2},

hence

E(Y_{d}(u) − Y_{d}(u′))^{2L} = 1 · 3 · · · · · (2L − 1)ρ_{α}(u, u′)^{2L} ≤ (2L)^{L}ρ_{α}(u, u′)^{2L}

with the metric ρ_{α} defined in (2.11) for arbitrary vectors u ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}}, u′ ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and L ≥ 1. In particular, with 2L = 2^{2(N+A)}M

\begin{aligned}E(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))^{2^{2(N+A)}M} & ≤ (2^{2(N+A)}M)^{2^{2(N+A)}M/2} · (2^{−2N}M^{−(d−1)/2})^{2^{2(N+A)}M} \\ & = (2^{(A−N)}M^{−(d−2)/2})^{2^{2(N+A)}M} \end{aligned}

(8.1) for all u^{(t)} ∈ U and u^{(t′)} ∈ U if U ∈ U(r, N). As a consequence,

E [ sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈U, u^{(t′)}∈U}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))]^{2^{2(N+A)}M}

≤ ∑_{(u^{(t)},u^{(t′)}): u^{(t)}∈U, u^{(t′)}∈U} E(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))^{2^{2(N+A)}M}

≤ r^{2}(M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} ≤ (2M^{−(d−2)/2} · 2^{(A−N)})^{2^{2(N+A)}M}

≤ (CM^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}

if N ≥ N_{0}(r) with some threshold N_{0}(r) and constant C ≥ 2, i.e. relation (5.7) holds for N ≥ N_{0} with C = C(d) ≥ 2 and A ≥ A_{0} ≥ 0.

Hence it is enough to show that relation (5.7) holds for a set U ∈ U(r, N) if it holds for all sets U ∈ U(r, N + 2). To show this let us consider such a partition u^{(l)} + U_{l}, 1 ≤ l ≤ L of the set U ∈ U(r, N) with L ≤ 2^{C2^{2N} M} elements which satisfies Lemma 6.2. First the following weaker estimate will be verified.

Let us take an element u^{(l)} + U_{l} of the partition of the set U we consider, and let us denote it by Ū_{l}. We will show that

\begin{matrix}E [  sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈Ū_{l}, u^{(t′)}∈Ū_{l}}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))]^{2^{2(N+A)}M} \\ ≤ (\frac{C}{3} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} \end{matrix}  (8.2)

for all A ≥ A_{0} with some threshold index A_{0} and the same constant C = C(d) which appears in (5.7) (with parameter N + 2) if these constant (depending only on the parameter d) are chosen sufficiently large.

To prove relation (8.2) let us consider two arbitrary vectors u ∈ Ū_{l} and u′ ∈ Ū_{l}, write them in the form u = u^{(l)} +u^{(0)} and u′ = u^{(l)} +u′^{(0)} with u^{(0)} ∈ U_{l} and u′^{(0)} ∈ U_{l}. We can write the difference Y_{d}(u) − Y (u′) because of the special form of the expression Y_{d}(u) defined in relation (2.1) as

\begin{aligned}Y_{d}(u) − Y_{d}(u′) & = Y_{d}(u^{(l)} + u^{(0)}) − Y_{d}(u^{(l)} + u′^{(0)}) = Y_{d}(u^{(0)}) − Y_{d}(u′^{(0)}) \\ & + ∑_{I: I⊂\{1,...,d−1\}, 1≤|I|≤d−2} M^{−|I|/2} [Y_{u^{(l)}}^{I}(u^{(0)}) − Y_{u^{(l)}}^{I}(u′^{(0)})] , \end{aligned}

(8.3)

where

Y_{u^{(l)}}^{I}(v) = ∑_{(i_{j}, j∈{1,...,d−1}\I} b_{u^{(l)}}^{I}(i_{j}, j ∈ {1, …, d} \ I) ∏_{j∈{1,...,d−1}\I} v_{j}(i_{j})g_{d}(i_{d})

for all v = (v_{1}(i_{1}), …, v_{d−1}(i_{d−1})) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}} and I ⊂ {1, …, d − 1}, 1 ≤ |I| ≤ d − 2 with the constants b_{u^{(l)}}^{I}(i_{j}, j ∈ {1, …, d} \ I) defined in (6.1). (Here we apply this formula with the choice u = u^{(l)},) and (g_{d}(1), …, g_{d}(n_{d})) is the same vector of independent, standard Gaussian random variables which appeared in the definition of Y_{d}(u).)

In the subsequent considerations the following notation will be applied. Given some vector u^{(t)} ∈ Ū_{l}, its decomposition to the vector u^{(l)} plus a vector in U_{l} will be denoted as u^{(t)} = u^{(l)} + u^{(t,0)} with u^{(t,0)} ∈ U_{l}.

By taking the supremum of the expressions both at the left-hand and right-hand side of identity (8.3) for all pairs (u^{(t)}, u^{(t′)}) such that u^{(t)} ∈ Ū_{l} and u^{(t′)} ∈ Ū_{l} we get an identity that implies the following inequality.

sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈Ū_{l}, u^{(t′)}∈Ū_{l}}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)})) ≤ Z + ∑_{I: I⊂{1,...,d−1}, 1≤|I|≤d−2} M^{−|I|/2}Z_{I}

(8.4)

with

Z = Z(l, N) = sup_{(u^{(t,0)},u^{(t′,0)}): u^{(t)}∈U_{l}, u^{(t′,0)}∈U_{l}}(Y_{d}(u^{(t,0)}) − Y_{d}(u^{(t′,0)}))

and

Z_{I} = Z_{I}(l, N) = sup_{(u^{(t,0)},u^{(t′,0)}): u^{(t)}∈U_{l}, u^{(t′,0)}∈U_{l}}[Y_{u^{(l)}}^{I}(u^{(t,0)}) − Y_{u^{(l)}}^{I}(u^{(t′,0)})],
for all I ⊂ {1, …, d − 1} such that 1 ≤ |I| ≤ d − 2.

I claim that

EZ^{2^{2(N+A)}M} ≤ (\frac{C}{4} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}  (8.5)

with the same constant C = C(d) as in formula (5.7) if A ≥ A_{0} with some fixed number A_{0} = A_{0}(d) ≥ 0, and

EZ_{I}^{2^{2(N+A)}M} ≤ (C′M^{−(d−|I|−2)/2}2^{(A−N)})^{2^{2(N+A)}M}  (8.6)

for all I ⊂ {1, …, d − 1} such that 1 ≤ |I| ≤ d − 2 if A ≥ A_{0} with some universal constants A_{0} and C′. Let me emphasize in particular that the constants A_{0} and C′ in (8.6) do not depend on the choice of the constant C = C(d) and threshold index A_{0} in (5.7).

Relation (8.5) can be deduced from our inductive hypothesis by which the Main inequality holds for N + 2 and the fact that U_{l} ∈ U(r, N + 2). Indeed, this inductive hypothesis together with Hölder’s inequality yield that

EZ^{2^{2(N+A)}M} = E [ sup_{((u^{(t,0)},u^{(t′,0)})): u^{(t,0)}∈U_{l}, u^{(t′,0)}∈U_{l}}(Y_{d}((u^{(t,0)}) − Y_{d}(u^{(t′,0)})]^{2^{2(N+A)}M}

≤ [E [ sup_{((u^{(t,0)},u^{(t′,0)})): u^{(t,0)}∈U_{l}, u^{(t′,0)}∈U_{l}}(Y_{d}((u^{(t,0)}) − Y_{d}(u^{(t′,0)})]^{2^{2(N+A+2)}M} ]^{1/4}

≤ (CM^{−(d−2)/2}2^{(A−(N+2))})^{2^{2(N+A+2)M} /4} = (\frac{1}{4}CM^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} .

(The reason for applying the induction from N +2 and not from N +1 to N in our proof is that in such a way we got a coefficient \frac{1}{4} at the right-hand side of estimate (8.5). An induction from N + 1 to N would yield only a weaker estimate with multiplying factor \frac{1}{2} which would be not sufficient for our purposes.)

Relation (8.6) will be proved first only in the case 1 ≤ |I| ≤ d − 3. This will be done with the help of the Main inequality with parameter d − |I| ≤ d − 1. This is legitime because of our inductive hypothesis. The main inequality will be applied for the operator B_{u^{(l)}}^{I} defined in (6.2) as the operator A and the set of vectors U ∈ U(r, N) will be chosen as U = U_{l}(I) = {u_{I^{c}}^{(t,0)}: u^{(t,0)} ∈ U_{l}}. That is we get the set U by taking the vectors u = (u_{1}, …, u_{d−1}) ∈ U_{l} and omitting their coordinates indexed by the elements of the set I. More precisely, we apply the Main inequality for a version of B_{u^{(l)}}^{I} and U_{l}(I) we get by renumerating the indices of their coordinates to the sets {1, …, d − |I|} and {1, …, d − |I| − 1} respectively in an appropriate way. A good way of reindexation of the coordinates is to list them with monotone increasing indices and to give then the j-th element the index j.

To apply the Main inequality we have to show that its conditions are satisfied with such a choice. We have to check that the operator B_{u^{(l)}}^{I} satisfies relation (5.6). (Here d − |I| takes the role of the parameter d.) This statement follows from the analogous statement for the operator A. Beside this, we have to show that U_{l}(I) ∈ U_{B_{u^{(l)}}^{I} ,M,d−|I|}(r, N). This can be done with the help of Lemma 6.2.

The estimate we have to give on ρ̄_{α_{u^{(l)}}^{I}} (·, ·) to show that U_{l}(I) ∈ U(r, N) =

U_{B_{u^{(l)}}^{I} ,M,d−|I|}(r, N) agrees with the estimate we proved in Lemma 6.2 on this quan-

tity. The bound we have to give about α̃_{j,k} to show that U_{l}(I) ∈ U_{B_{u^{(l)}}^{I} ,M,d−|I|}(r, N)

follows from relation (7.3) and the inequality α̃_{j,k}(u_{j}) ≤ α̃_{k}^{I}(u^{(l)}) if u_{j} ∈ B^{n_{j}} with the same quantities α̃_{j,k}(u_{j}) and α̃_{k}^{I}(u^{(l)}) which appeared in the proof of Lemma 6.2. The remaining properties needed to check that U_{l}(I) ∈ U_{B_{u^{(l)}}^{I} ,M,d−|I|}(r, N) clearly hold. Then

the Main inequality may be applied with such a choice, and this yields relation (8.6) for 1 ≤ |I| ≤ d − 3.

In the case |I| = d − 2 the set {1, …, d − 1} \ I consists of a point k, and formula (8.6) can be proved with the help of the Main inequality in the case d = 2 in a similar way. This inequality can be applied for the operator 2^{N}B_{u^{(l)}}^{I} defined as 2^{N}B_{u^{(l)}}^{I}(v) = ∑_{i_{k},i_{d}} 2^{N}b_{u^{(l)}}^{I}(i_{k}, i_{d})v(i_{k}, i_{d}) for a vector v ∈ R^{n_{k}} ⊗ R^{n_{d}} as the operator A. It follows from

Lemma 6.2 that

α_{2}(u^{(t,0)} −u^{(t′,0)}) = [∑_{i_{d}} (∑_{i_{k}} 2^{N}b_{u^{(l)}}^{I}(i_{k}, i_{d})[u_{I^{c}}^{(t,0)}(i_{k}) − u_{I^{c}}^{(t′,0)}(i_{k})])^{2}]^{1/2}≤ 2^{−N}M^{−1/2}

if u^{(t,0)}(i_{k}) ∈ U_{l} and u^{(t′,0)}(i_{k}) ∈ U_{l}. Hence the set consisting of all vectors of the form \frac{1}{2}(u_{I^{c}}^{(t,0)} − u_{I^{c}}^{(t,0)}) with some u^{(t,0)} ∈ U_{l} and u^{(t′,0)} ∈ U_{l} is contained in the set U_{N} introduced in (3.2). The inequality α_{1}(2^{N}B_{u^{(l)}}^{I}) ≤ 1 also holds by formula (7.4). Hence the Main inequality in the case d = 2 can be applied in this case, and it yields that E(2^{N}Z_{I})^{2^{2(N+A)}M} ≤ (C · 2^{A})^{2^{2(N+A)}M} which is equivalent to (8.6) for |I| = d − 2.

Inequality (8.2) follows from relations (8.4), (8.5), (8.6) and Minkowski’s inequality for L_{p} norms with p = 2^{2(N+A)}M. (Observe that we are working with non-negative random variables, since the suprema we consider contain the terms Y_{d}(u^{(t)})−Y_{d}(u^{(t)}) ≡ 0.) Indeed, they yield that

\begin{matrix}E [ sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈Ū_{l}, u^{(t′)}∈Ū_{l}}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))]^{2^{2(N+A)}M} \\ ≤ ((\frac{C}{4} + 2^{d}C′) M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} . \end{matrix}

If the constant C = C(d) in the Main inequality is chosen sufficiently large, then \frac{C}{4} + 2^{d}C′ ≤ \frac{C}{3} in the last inequality, and this means that it implies relation (8.2).

The Main inequality will be proved with the help of inequality (8.2). It will be also exploited that the cardinality of the partition of a set U in Lemma 6.2 is not too large.

Let us consider a partition Ū_{l} = u^{(l)} + U_{l}, 1 ≤ l ≤ L, of a set U ∈ U(r, N) with L ≤ 2^{C2^{2N} M} elements that satisfies Lemma 6.2. Let us fix an element ū^{(l)} ∈ Ū_{l} in all sets Ū_{l}, 1 ≤ l ≤ L. Given a vector u^{(t)} ∈ U let ℓ(t) denote that index l, 1 ≤ l ≤ L, for which u^{(t)} ∈ Ū_{l}. Then we can write for two arbitrary vectors u^{(t)} ∈ U and u^{(t′)} ∈ U the inequality

|Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)})| ≤ [Y_{d}(u^{(t)}) − Y_{d}(ū^{ℓ(t)})] + [Y_{d}(u^{(t′)}) − Y_{d}(ū^{ℓ(t′)})]
+ [Y_{d}(ū^{ℓ(t′)}) − Y_{d}(ū^{ℓ(t)})]

≤ 2 sup_{1≤l≤L} sup_{u^{(s)}: u^{(s)}∈Ū_{l}}[Y_{d}(u^{(s)}) − Y_{d}(ū^{(l)}] + sup_{1≤l,l′≤L}[Y_{d}(ū^{(l′)}) − Y_{d}(ū^{(l)})].

Since the right-hand side of the above inequality does not depend on the vectors u^{(t)} ∈ U and u^{(t′)} ∈ U it implies that

sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈U, u^{(t′)}∈U}[Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)})]

≤ 2 sup_{1≤l≤L} sup_{u^{(s)}: u^{(s)}∈Ū_{l}}[Y_{d}(u^{(s)}) − Y_{d}(ū^{(l)}] + sup_{1≤l,l′≤L}[Y_{d}(ū^{(l′)}) − Y_{d}(ū^{(l)})].

(8.7)

The Main inequality can be proved by means of good moment estimates on the two terms at the right-hand side of inequality (8.7). It follows from inequalities (8.2) and L ≤ 2^{C′2^{2N} M} for the number of partitions of U in Lemma 6.2, where the number C′ does not depend on the constants A_{0} = A_{0}(d) and C = C(d) in the Main inequality that

E (2 sup_{1≤l≤L} sup_{u^{(s)}: u^{(s)}∈Ū_{l}}[Y_{d}(u^{(s)}) − Y_{d}(ū^{(l)}])^{2^{2(N+A)}M}

≤ ∑_{l=1}^{L} E (2 sup_{(u^{(s)},u^{(s′)}): u^{(s)}∈Ū_{l}, u^{(s′)}∈U_{l}}[Y_{d}(u^{(s)}) − Y_{d}(ū^{(s′)}])^{2^{2(N+A)}M}

≤ L (\frac{2C}{3} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}

≤ 2^{C′2^{2N} M} (\frac{2C}{3} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}  (8.8)

= (2^{C′2^{−2A}} \frac{2C}{3} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} ≤ (\frac{3C}{4} M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}

if the threshold index A_{0} in the Main inequality is chosen so large that 2^{C′2^{−2A}} ≤ \frac{9}{8} for A ≥ A_{0}. Such a choice is possible since the constant C′ appearing in the exponent of the bound for the cardinality of the partition of the set U does not depend on the choice of the number A_{0} in the Main inequality. (The threshold index A_{0} was introduced to have a control on the multiplicative factor L in the previous estimate.)

We get in a similar way with the help of inequality (8.1)

E ( sup_{1≤l,l′≤L}[Y_{d}(ū^{(l′)}) − Y_{d}(ū^{(l)})])^{2^{2(N+A)}M} ≤ ∑_{1≤l,l′≤L} E ([Y_{d}(ū^{(l′)}) − Y_{d}(ū^{(l)})])^{2^{2(N+A)}M}

≤ L^{2} (M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} ≤ 2^{2C′2^{2N} M} (M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}
≤ (C̄M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}  (8.9)

with a constant C̄ which does not depend on the constant C = C(d) in the Main inequality.

It follows from relations (8.7), (8.8), (8.9) and Minkowski’s inequality for L_{p} norms with p = 2^{2(N+A)}M (we are working again with non-negative random variables) that

E [ sup_{(u^{(t)},u^{(t′)}): u^{(t)}∈U, u^{(t′)}∈U}(Y_{d}(u^{(t)}) − Y_{d}(u^{(t′)}))]^{2^{2(N+A)}M}

≤ ((\frac{3C}{4} + C̄) M^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M} ≤ (CM^{−(d−2)/2}2^{(A−N)})^{2^{2(N+A)}M}

if the constant C = C(d) (together with A_{0} = A_{0}(d)) is chosen sufficiently large. The Main inequality is proved.

Appendix. The proof of Propositions 4.1 and 4.2.

The proof of Proposition 4.1. Put K = {y: y ∈ R^{n}, α_{1}(y) ≤ 4α_{1}(tG), α_{2}(y) ≤ 4α_{2}(tG)\}. Then μ_{n,t}(K) ≥ \frac{1}{2}, since by the Markov inequality

1 − μ_{n,t}(K) ≤ μ_{n,t}(y: α_{1}(y) > 4tEα_{1}(tG)) + μ_{n,t}(y: α_{2}(y) > 4tEα_{2}(tG)) ≤ \frac{1}{2}.

Beside this, the set K has the symmetry property −K = K which yields that

μ_{n,t}(y: y ∈ R^{n}, α_{1}(y − x) ≤ 4Eα_{1}(tG), α_{2}(y − x) ≤ 4Eα_{2}(tG))

= C_{n} ∫_{K+x} e^{−y^{2}/2t^{2}} dy = C_{n} ∫_{K} e^{−(y+x)^{2}/2t^{2}} dy = e^{−∥x∥^{2}/2t^{2}} ∫_{K} e^{(y,x)/t^{2}}μ_{n,t}( dy)

= e^{−∥x∥^{2}/2t^{2}} ∫_{K} \frac{1}{2} (e^{(y,x)/t^{2}} + e^{(−y,x)/t^{2}}) μ_{n,t}( dy) ≥ e^{−∥x∥^{2}/2t^{2}}μ_{n,t}(K)

with the norming constant C_{n} = (\sqrt{2π}t)^{−n}. Hence the relations μ_{n,t}(K) ≥ \frac{1}{2}, and ∥x∥ ≤ 1 (i.e. x ∈ B^{n}) imply that

μ_{n,t}({y: y ∈ R^{n}, α_{1}(y − x) ≤ 4Eα_{1}(tG), α_{2}(y − x) ≤ 4Eα_{2}(tG)})

≥ \frac{1}{2}e^{−∥x∥^{2}/2t^{2}} ≥ \frac{1}{2}e^{−1/2t^{2}}.

The proof of Proposition 4.2. In the case d = 1 Proposition 4.2 immediately follows from Proposition 4.1 if it is applied for α = α_{1} = α_{2}, and the relation 4Eα(tG_{n}) = Eα(4tG_{n}) is exploited. Hence it is enough to prove Proposition 4.2 for d under the inductive hypothesis that it holds for d − 1.

Let us fix some x = (x_{1}, …, x_{d}) ∈ B^{n_{1}} × ⋯ × B^{n_{d}}, where B^{n} denotes the unit ball in R^{n}. We can write

\begin{aligned}ρ_{α}(x, y) & = α(y_{1} ⊗ ⋯ ⊗ y_{d−1} ⊗ y_{d} − x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ x_{d}) \\ & ≤ α(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ (y_{d} − x_{d})) + α((y_{1} ⊗ ⋯ ⊗ y_{d−1} − x_{1} ⊗ ⋯ x_{d−1}) ⊗ y_{d}) \end{aligned}

(A1)

for arbitrary y = (y_{1}, …, y_{d}) ∈ R^{n_{1}} × ⋯ × R^{n_{d}}.

We shall define some sets A, B and C. We shall not denote their dependence on the vector x ∈ B^{n_{1}} × ⋯ × B^{n_{d}} we have fixed. To define the set A first we introduce the following quantity W_{I}^{x}(y|α, t) similar to the quantity W_{I}^{x}(α, t) defined in formula (4.2).

Let us fix d independent standard normal vectors G_{j} = (g_{j}(1), …, g_{j}(n_{j})) of dimension n_{j}, 1 ≤ j ≤ d, and define for all t > 0, y ∈ R^{n_{d}} and I ⊂ {1, …, d}, I ≠ ∅ the quantity

W_{I}^{x}(y|α, t) = Eα(z_{1} ⊗ ⋯ ⊗ z_{d}) where z_{j} = tG_{j} if j ∈ I,
z_{j} = x_{j} if j ∉ I and j ≠ d, and z_{d} = y if d ∉ I.

Then we put

A = {y_{d}: y_{d} ∈ R^{n_{d}}, α(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ (y_{d} − x_{d})) ≤ Eα(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ 4tG_{d}),

∑_{I: I⊂{1,...,d−1}, I≠∅}W_{I}^{x}(y_{d} − x_{d})|α, 4t) ≤ ∑_{I: I⊂{1,...,d}, d∈I, I∩{1,...,d−1}≠∅}W_{I}^{x}(α, 4t)},

B = {y = (y_{1}, …, y_{d}): y ∈ R^{n_{1}} × ⋯ × R^{n_{d}},

α((y_{1} ⊗ ⋯ ⊗ y_{d−1} − x_{1} ⊗ ⋯ ⊗ x_{d−1}) ⊗ y_{d}) ≤ ∑_{I: I⊂{1,...,d−1}, I≠∅}W_{I}^{x}(y_{d}|α, 4t)}

and

C = B ∩ {y = (y_{1}, …, y_{d}): y ∈ R^{n_{1}} × ⋯ × R^{n_{d}}, y_{d} ∈ A}.

I claim that the inequalities

μ_{n_{d},t}(A) ≥ \frac{1}{2}e^{−1/2t^{2}}  (A2)

and

\begin{matrix}μ_{n_{1}+···+n_{d−1},t}(B ∩ ((R^{n_{1}} × ⋯ × R^{n_{d−1}}) × y_{d})) ≥ 2^{−(d−1)}e^{−(d−1)/2t^{2}} \\ for all y_{d} = (y_{d}(1), …, y_{d}(n_{d})) ∈ R^{n_{d}} \end{matrix}  (A3)

hold, where (R^{n_{1}} × ⋯ × R^{n_{d−1}}) × y_{d} = {(y_{1}, …, y_{d−1}, y_{d}): (y_{1}, …, y_{d−1}) ∈ R^{n_{1}} × ⋯ × R^{n_{d−1}}}.

Relation (A2) follows from the identity 4Eα(tG_{n}) = Eα(4tG_{n}) and Proposition 4.1

with the choice α_{1}(z) = α(x_{1}⊗⋯⊗x_{d−1}⊗z) and α_{2}(z) = ∑_{I: I⊂{1,··· ,d−1}, I≠∅} W_{I}^{x}(z|α, 4t)

for z ∈ R^{n_{d}}. Observe that both α_{1}(·) and α_{2}(·) are pseudonorms in R^{n_{d}}, hence Proposition (4.1) is applicable for them.

Relation (A3) follows from Proposition 4.2 with parameter d − 1 if it is applied for the pseudonorm ᾱ_{y_{d}} on R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d−1}} defined by the formula ᾱ_{y_{d}}(u) = α(u ⊗ y_{d}) for u ∈ R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d−1}} with a fixed y_{d} ∈ R^{n_{d}}. Here u ⊗ y_{d} is that function in R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} for which u ⊗ y_{d}(i_{1}, …, i_{d}) = u(i_{1}, …, i_{d−1})y_{d}(i_{d}) for all 1 ≤ i_{j} ≤ n_{j}, 1 ≤ j ≤ d. Observe that ᾱ_{u_{d}} is really a pseudonorm for all y_{d} ∈ R^{n_{d}}, hence we can apply Proposition 4.2 with parameter d − 1 for it.

Relations (A2), (A3) and the Fubini theorem imply that

μ_{n_{1}+···+n_{d},t}(C) ≥ 2^{−d}e^{−d/2t^{2}}.  (A4)

Indeed, μ_{n_{1}+···+n_{d−1},t}(B ∩((R^{n_{1}} ×⋯×R^{n_{d−1}})×y_{d})) ≥ 2^{−(d−1)}e^{−(d−1)/2t^{2}} for all points y_{d} ∈ R^{n_{d}} by relation (A3). We get relation (A4) from this inequality, relations (A2) and the Fubini theorem by integrating this inequality on the set {y_{d} ∈ A} with respect to the measure μ_{n_{d},t}.

Finally, I claim that

C ⊂ {y = (y_{1}, …, y_{d}): y ∈ R^{n_{1}} × ⋯ × R^{n_{d}}, ρ_{α}(x, y) ≤ ∑_{I: I⊂{1,...,d}, I≠∅} W_{I}^{x}(α, 4t)} .

(A5)

Indeed, if y = (y_{1}, …, y_{d}) ∈ C, then

ρ_{α}(x, y) ≤ α(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ (y_{d} − x_{d})) + α((y_{1} ⊗ ⋯ ⊗ y_{d−1} − x_{1} ⊗ ⋯ x_{d−1}) ⊗ y_{d})

≤ Eα(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ 4tG_{d}) + ∑_{I: I⊂{1,...,d−1}, I≠∅} W_{I}^{x}(y_{d}|α, 4t)

≤ Eα(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ 4tG_{d}) + ∑_{I: I⊂{1,...,d−1}, I≠∅} W_{I}^{x}(y_{d} − x_{d}|α, 4t)

+ ∑_{I: I⊂{1,...,d−1}, I≠∅} W_{I}^{x}(α, 4t)

≤ Eα(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ 4tG_{d}) + ∑_{I: I⊂{1,...,d}, d∈I, I∩{1,...,d−1}≠∅} W_{I}^{x}(α, 4t)

+ ∑_{I: I⊂{1,...,d−1}, I≠∅} W_{I}^{x}(α, 4t) = ∑_{I: I⊂{1,...,d}, I≠∅} W_{I}^{x}(α, 4t).

The first inequality of this series of inequalities holds because of relation (A1). The second inequality was based on the first relation in the definition of the set A and on the definition of the set B. The third inequality is valid because of the relation α(z ⊗ y) ≤ α(z ⊗ x) + α(z ⊗ (y − x)) for arbitrary pseudonorm α on the tensor product R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d}} and z ∈ R^{n_{1}} ⊗ ⋯ ⊗ R^{n_{d−1}}. The last inequality follows from the second relation in the definition of the set A. In the closing step we have applied the identity Eα(x_{1} ⊗ ⋯ ⊗ x_{d−1} ⊗ 4tG_{d}) = W_{{d}}^{x}(α, 4t).

Proposition 4.2 is a simple consequence of relations (A4) and (A5).

References:

1.) Adamczak, R. (2006) Moment inequalities for U-statistics. Annals of Probability 34, 2288–2314

2.) de la Peña, V. H. and Montgomery–Smith, S. (1995) Decoupling inequalities for the tail-probabilities of multivariate U-statistics. Ann. Probab., 23, 806–816

3.) Latała, R. (2006) Estimates of moments and tails of Gaussian chaoses. Annals of Probability 34 2315–2331

4.) Ledoux, M. (2001) The concentration of measure phenomenon. Mathematical Surveys and Monographs 89 American Mathematical Society, Providence, RI.

5.) Major, P. (2007) On a multivariate version of Bernstein’s inequality. Electronic Journal of Probability 12 966–988