1. Introduction

Let \(\Omega\) be a compact subset of \({\mathbb R}^d\) with a probability measure \(\mu\). By the \(L_q\), \(1\le q< \infty \), norm we mean

$$\|f\|_q:=\|f\|_{L_q(\Omega)} := \left(\,\intop_\Omega |f|^q\,d\mu\right)^{\!1/q}.$$

By discretization of the \(L_q\) norm we understand a replacement of the measure \(\mu\) by a discrete measure \(\mu_m\) with support on a set \(\xi =\{\xi^j\}_{j=1}^m \subset \Omega\). This means that integration with respect to the measure \(\mu\) is replaced by an appropriate cubature formula. Thus, integration is substituted by evaluation of a function \(f\) at a finite set \(\xi\) of points. This is why we call this way of discretization sampling discretization. Discretization is a very important step in making a continuous problem computationally feasible. The reader can find a corresponding discussion in the recent survey [6]. The first results in sampling discretization were obtained in the 1930s by Marcinkiewicz as well as by Marcinkiewicz and Zygmund (see [29]) for discretization of the \(L_q\) norms of the univariate trigonometric polynomials. We call discretization results of this kind the Marcinkiewicz type theorems. Recently, substantial progress in sampling discretization has been made in [4–6, 13, 15, 26, 27]. To discretize the integral norms successfully, a new technique was introduced. This technique takes different forms in different papers, but the common feature of its forms is the following. The new sampling discretization technique is a combination of a probabilistic technique, including the chaining technique, with results on the entropy numbers in the uniform norm (or its variants). Fundamental results from [2, 17, 20] were used. The reader can find results on chaining in [14, 23] and on the generic chaining in [20]. We note that the idea of the chaining technique goes back to the 1930s, when it was suggested by A. N. Kolmogorov. Later, results of this type have been developed in the study of the central limit theorem in probability theory (see, for instance, [8]). The reader can also find general results on metric entropy in [3; 16, Ch. 15; 19; 23, Ch. 3; 28, Ch. 7] and in the recent papers [9, 25]. Bounds for the entropy numbers of function classes are important in themselves, and they also have important connections with other fundamental problems (see, for instance, [23, Ch. 3] and [7, Ch. 6]).

We now proceed to the detailed presentation.

Marcinkiewicz problem.

Let \(\Omega\) be a compact subset of \({\mathbb R}^d\) with a probability measure \(\mu\). We say that a linear subspace \(X_N\) (the index \(N\) usually stands for the dimension of \(X_N\)) of \(L_q(\Omega)\), \(1\le q < \infty \), admits the Marcinkiewicz type discretization theorem with parameters \(m\in{\mathbb N}\) and \(q\) and positive constants \(C_1\le C_2\) if there exists a set

$$\bigl\{\xi^j \in\Omega \colon\, \,j=1,\dots,m\bigr\}$$

such that for any \(f\in X_N\) we have

$$ C_1\|f\|_q^q \le \frac{1}{m} \sum_{j=1}^m |f(\xi^j)|^q \le C_2\|f\|_q^q.$$
(1.1)

In the case \(q= \infty \) we define \(L_ \infty \) as the space of continuous functions on \(\Omega\) and ask for

$$ C_1\|f\|_ \infty \le \max_{1\le j\le m}\mathopen|f(\xi^j)| \le \|f\|_ \infty .$$
(1.2)

We will also use the following brief way to express the above properties: the \( {\mathcal M} (m,q)\) (more precisely, the \( {\mathcal M} (m,q,C_1,C_2)\)) theorem holds for a subspace \(X_N\), written \(X_N \in {\mathcal M} (m,q)\) (more precisely, \(X_N \in {\mathcal M} (m,q,C_1,C_2)\)).

Our main interest in this paper is to discuss the Marcinkiewicz problem in the case when \(X_N\) is a subspace of the trigonometric polynomials with frequencies (harmonics) from a hyperbolic cross. By \(Q\) we denote a finite subset of \({\mathbb Z}^d\), and \(|Q|\) stands for the number of elements in \(Q\). Let

$${\mathcal T} (Q):= \Biggl\{f \colon\, \,f=\sum_{ {\mathbf k} \in Q}c_ {\mathbf k} e^{i( {\mathbf k} , {\mathbf x} )},\ c_{ {\mathbf k} }\in{\mathbb C}\Biggr\}.$$

For \( {\mathbf s} \in{\mathbb Z}^d_+\) define

$$\rho( {\mathbf s} ) := \bigl\{ {\mathbf k} \in{\mathbb Z}^d \colon\, \,[2^{s_j-1}] \le |k_j| < 2^{s_j}, \ j=1,\dots,d\bigr\},$$

where \([x]\) denotes the integer part of \(x\). We define the step hyperbolic cross \(Q_n\) as

$$Q_n := \bigcup_{ {\mathbf s} \colon\, \| {\mathbf s} \|_1\le n} \rho( {\mathbf s} )$$

and the corresponding set of hyperbolic cross polynomials as

$${\mathcal T} (Q_n) := \Biggl\{f \colon\, \,f=\sum_{ {\mathbf k} \in Q_n} c_ {\mathbf k} e^{i( {\mathbf k} , {\mathbf x} )}\Biggr\}.$$

In addition to the step hyperbolic cross \(Q_n\), we also consider a more general step hyperbolic cross \(Q_n^\gamma\), where \(\gamma = (\gamma_1,\dots,\gamma_d)\) has the form \(1=\gamma_1=\dots=\gamma_\nu< \gamma_{\nu+1} \le \dots\le \gamma_d\) with \(\nu\in{\mathbb N}\), \(\nu \le d\):

$$Q_n^\gamma := \bigcup_{ {\mathbf s} \colon\, (\gamma, {\mathbf s} )\le n} \rho( {\mathbf s} ).$$

It is clear that in the case \(\gamma = {\mathbf 1} := (1,\dots,1)\) we have \(Q_n^{\mathbf 1} = Q_n\). In this paper we are primarily interested in the Marcinkiewicz type discretization theorems for the hyperbolic cross trigonometric polynomials from \( {\mathcal T} (Q_n^\gamma)\).

The most complete results on sampling discretization are obtained in the case \(q=2\). The problem is basically solved in the case of subspaces of trigonometric polynomials \( {\mathcal T} (Q)\) with arbitrary \(Q\). In [26] it was shown how to derive the following result from the recent paper by S. Nitzan, A. Olevskii, and A. Ulanovskii [18], which in turn is based on the paper of A. Marcus, D. A. Spielman, and N. Srivastava [17].

Theorem 1.1.

There are three positive absolute constants \(C_1,\) \(C_2,\) and \(C_3\) with the following properties: For any \(d\in{\mathbb N}\) and any \(Q\subset {\mathbb Z}^d\) there exists a set of \(m\le C_1|Q|\) points \(\xi^j\in {\mathbb T} ^d,\) \(j=1,\dots,m,\) such that for any \(f\in {\mathcal T} (Q)\) we have

$$C_2\|f\|_2^2 \le \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^2 \le C_3\|f\|_2^2.$$

In other words, there exist three positive absolute constants \(C_1\), \(C_2\), and \(C_3\) such that for any \(Q\subset {\mathbb Z}^d\) we have \( {\mathcal T} (Q) \in {\mathcal M} (m,2,C_2,C_3)\) provided \(m\ge C_1|Q|\). We now restrict ourselves to the case \(q\in [1, \infty )\), \(q\neq 2\), and \(Q=Q_n^\gamma\). In this paper we provide some bounds on \(m\) which guarantee that \( {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q)\). The following theorem is the main result of the paper.

Theorem 1.2.

For \(q\in [1, \infty )\) and \(\gamma,\) where \(\gamma = (\gamma_1,\dots,\gamma_d)\) has the form \(1=\gamma_1=\dots=\gamma_\nu< \gamma_{\nu+1} \le \dots\le \gamma_d\) with \(\nu\in{\mathbb N},\) \(\nu \le d,\) there are three positive constants \(C_i=C_i(q,\gamma),\) \(i=1,2,3,\) such that we have

$${\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q,C_2,C_3)\qquad \textit{provided}\quad m\ge C_1|Q_n^\gamma|n^{w(\nu,q)},$$

where

$$w(\nu,q) = \begin{cases} \displaystyle 3, & \textit{ }\, \displaystyle q=1,\\\displaystyle 2, & \textit{ }\, \displaystyle q\in (1,2],\\\displaystyle (\nu-1)(q-2) + \min\{q,3\}, & \textit{ }\, \displaystyle q> 2.\end{cases}$$

We point out that in the case \(\nu=1\) the exponent of the extra factor in the bound for \(m\) does not grow with \(q\): \(w(1,q)\le 3\). Theorem 1.2 improves the corresponding result of É. S. Belinskii [1]. In [1] there is the following condition on the number of sampling points: \(m\ge C_1|Q_n^\gamma|n^{\max\{(d-1)(q-2),0\}+4}\). Theorem 1.2 improves the bound from [1] for all \(q\in [1, \infty )\). We note that in the case \(q=2\) Theorem 1.1 provides a stronger result than Theorem 1.2. In the case \(q\in [1,3]\) Theorem 1.2 follows from known general results. A new bound proved in this paper corresponds to the case \(q\in (3, \infty )\). We present this proof in Section 2. In Section 3 we discuss the entropy numbers of the unit \(L_q\) balls of \( {\mathcal T} (Q_n^\gamma)\) in the uniform norm. Finally, in Section 4 we discuss an extension of Theorem 1.2 to the case of arbitrary \(Q\subset {\mathbb Z}^d\).

Theorem 1.2 does not cover the case \(q= \infty \). It is known that the sampling discretization results in the case \(q= \infty \) are fundamentally different from those in the case \(q\in [1, \infty )\). Theorem 1.2 shows that for all \(q\in [1, \infty )\) the condition \(m\ge C(q,d)|Q_n|n^{w(d,q)}\) is sufficient for \( {\mathcal T} (Q_n) \in {\mathcal M} (m,q)\). The extra factor \(n^{w(d,q)}\) is logarithmic in terms of \(|Q_n|\). A nontrivial surprising negative result was proved for \(q= \infty \) (see [10–12] and also [28, Theorem 7.5.17]). The authors proved that the necessary condition for \( {\mathcal T} (Q_n)\in {\mathcal M} (m, \infty )\) is \(m\ge C|Q_n|^{1+c}\) with absolute constants \(C,c>0\). We do not present new results for the case \(q= \infty \) in this paper. The reader can find further results and discussions concerning the case \(q= \infty \) in [6, 13].

There are many open problems in sampling discretization (see [6]). We now formulate one directly related to Theorems 1.1 and 1.2.

Open problem 1.

Is it true that for \(q\in [1, \infty )\), \(q\neq 2\), and \(\gamma\) there are three positive constants \(C_i=C_i(q,\gamma)\), \(i=1,2,3\), such that we have

$${\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q,C_2,C_3)\qquad \text{provided}\quad m\ge C_1|Q_n^\gamma|?$$

Throughout the paper the letter \(C\) denotes a positive constant, which may be different in different formulas. The notation \(C(q,d)\) means that the constant \(C\) may depend on the parameters \(q\) and \(d\). Sometimes it will be convenient for us to use the following notation. For two sequences \(\{a_k\}_{k=1}^ \infty \) and \(\{b_k\}_{k=1}^ \infty \) we write \(a_k \asymp b_k\) if there are two positive constants \(C_1\) and \(C_2\) independent of \(k\) such that \(C_1a_k \le b_k\le C_2 a_k\), \(k=1,2,\dots\).

2. General results and proof of Theorem 1.2

We begin with a simple remark on a connection between real and complex cases. Usually, general results are proved for real subspaces \(X_N\). Suppose that a complex subspace has a form

$${\mathcal C} _N = \bigl\{f = f_{\textrm{R}} + i f_{\textrm{I}} \colon\, \, f_{\textrm{R}} , f_{\textrm{I}} \in X_N\bigr\},$$

where \(X_N\) is a real subspace.

Proposition 2.1.

Let \(q\in [1, \infty )\). Suppose \(X_N\in {\mathcal M} (m,q,C_2,C_3)\). Then

$${\mathcal C} _N \in {\mathcal M} \bigl(m,q,2^{-q-1}C_2,2^{q+1}C_3\bigr).$$

Proof.

Using a simple inequality for a complex number \(z=x+iy\),

$$\max\{|x|,|y|\} \le |z| \le |x|+|y|,$$

we obtain the following inequalities. Let \(\xi=\{\xi^j\}_{j=1}^m\) be such that for all \(g\in X_N\)

$$ C_2 \|g\|_q^q \le \frac{1}{m} \sum_{j=1}^m |g(\xi^j)|^q \le C_3\|g\|_q^q.$$
(2.1)

Introduce the notation

$$g_\xi := (g(\xi^1),\dots,g(\xi^m)),\qquad f_{\textrm{R},\xi} := ( f_{\textrm{R}} )_\xi,\qquad f_{\textrm{I},\xi} := ( f_{\textrm{I}} )_\xi,$$

and

$$\|g_\xi\|_{\ell_{q,m}}^q := \frac{1}{m} \sum_{j=1}^m |g(\xi^j)|^q.$$

Then for \(f\in {\mathcal C} _N\) we obtain

$$\|f\|_q^q \le 2^q\bigl(\| f_{\textrm{R}} \|_q^q + \| f_{\textrm{I}} \|_q^q\bigr) \le 2^qC_2^{-1}\bigl(\| f_{\textrm{R},\xi} \|_{\ell_{q,m}}^q + \| f_{\textrm{I},\xi} \|_{\ell_{q,m}}^q\bigr) \le 2^{q+1}C_2^{-1}\|f_{\xi}\|_{\ell_{q,m}}^q$$

and

$$\|f_{\xi}\|_{\ell_{q,m}}^q \le 2^q\bigl(\| f_{\textrm{R},\xi} \|_{\ell_{q,m}}^q + \| f_{\textrm{I},\xi} \|_{\ell_{q,m}}^q\bigr) \le 2^qC_3\bigl(\| f_{\textrm{R}} \|_q^q +\| f_{\textrm{I}} \|_q^q\bigr) \le 2^{q+1}C_3\|f\|_q^q.$$

This proves Proposition 2.1. \(\quad\Box\)

Thus, it is sufficient to prove Theorem 1.2 for the subspace \( {\mathcal R} {\mathcal T} (Q_n^\gamma)\) of real trigonometric polynomials from \( {\mathcal T} (Q_n^\gamma)\). Our proof is based on conditional theorems. We now formulate the known conditional theorems.

We begin with the definition of the entropy numbers. Let \(X\) be a Banach space. Denote by \(B_X(y,r)\) a ball with center \(y\) and radius \(r\): \(B_X(y,r):=\{x\in X \colon\, \|x-y\|\le r\}\). For a compact set \(A\) and a positive number \(\varepsilon\), we define the covering number \(N_\varepsilon(A)\) as follows:

$$N_\varepsilon(A) := N_\varepsilon(A,X) :=\min \Biggl\{n \colon\, \,\exists y^1,\dots,y^n\in A \colon\, \, A\subseteq \bigcup_{j=1}^n B_X(y^j,\varepsilon)\Biggr\}.$$

Along with the entropy \(H_\varepsilon(A,X):= \log_2 N_\varepsilon(A,X)\), it is convenient to consider the entropy numbers \(\varepsilon_k(A,X)\):

$$\varepsilon_k(A,X) :=\inf\Biggl\{\varepsilon \colon\, \,\exists y^1,\dots,y^{2^k} \in A \colon\, \,A \subseteq \bigcup_{j=1}^{2^k} B_X(y^j,\varepsilon)\Biggr\}.$$

In our definition of \(N_\varepsilon(A)\) and \(\varepsilon_k(A,X)\) we require \(y^j\in A\). In a standard definition of \(N_\varepsilon(A)\) and \(\varepsilon_k(A,X)\) this restriction is not imposed. However, it is well known (see [23, p. 208]) that these characteristics may differ at most by a factor of \(2\). Throughout the paper we also use the following notation for the unit \(L_q\) ball of \(X_N\):

$$X_N^q:= \bigl\{f\in X_N \colon\, \, \|f\|_q \le 1\bigr\}.$$

The first conditional theorem in the sampling discretization was proved in [27] in the case \(q=1\).

Theorem 2.1.

Suppose that a subspace \(X_N\) satisfies the condition (\(B\ge 1\))

$$\varepsilon_k(X^1_N,L_ \infty ) \le B \begin{cases} \displaystyle \frac Nk, & \textit{ }\, \displaystyle k\le N,\\\displaystyle 2^{-k/N}, & \textit{ }\, \displaystyle k>N. \end{cases}$$

Then for a sufficiently large absolute constant \(C\) there exists a set of

$$m \le CNB\bigl(\log_2(2N\log_2(8B))\bigr)^2$$

points \(\xi^j\in\Omega,\) \(j=1,\dots,m,\) such that for any \(f\in X_N\) we have

$$\frac{1}{2}\|f\|_1 \le \frac{1}{m}\sum_{j=1}^m |f(\xi^j)| \le \frac{3}{2}\|f\|_1.$$

The proof of Theorem 2.1 in [27] is based on the concentration measure result from [2] (see [27, Lemma 2.1]) and on the elementary chaining type technique from [14] (see also [23, Ch. 4]). Theorem 2.1 was extended to the case \(q\in[1, \infty )\) in [4].

Theorem 2.2.

Let \(1\le q< \infty \). Suppose that a subspace \(X_N\) satisfies the condition

$$ \varepsilon_k(X^q_N,L_ \infty ) \le B \biggl( \frac Nk \biggr)^{\!1/q}, \qquad 1\leq k\le N,$$
(2.2)

where \(B\ge 1\). Then for a sufficiently large constant \(C(q)\) there exists a set of

$$m \le C(q)NB^{q}(\log_2(2BN))^2$$

points \(\xi^j\in\Omega,\) \(j=1,\dots,m,\) such that for any \(f\in X_N\) we have

$$\frac{1}{2}\|f\|_q^q \le \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^q \le \frac{3}{2}\|f\|_q^q.$$

Note the well-known fact that inequality (2.2) implies

$$\varepsilon_k(X^q_N,L_ \infty ) \le 6B\cdot 2^{-k/N}, \qquad k > N.$$

Just as the proof of Theorem 2.1, the proof of Theorem 2.2 in [4] is based on the concentration measure result from [2]. However, the chaining technique used in [4] differs from that in [27]. In [4] the corresponding \(\varepsilon\)-nets are built in a more delicate way than in [27] (sandwiching technique). In both Theorems 2.1 and 2.2 the conditions are formulated in terms of the entropy numbers in the uniform norm \(L_ \infty \). Very recently, a new idea in this direction was developed in [15]. E. Kosov in [15] proves the corresponding theorem with the conditions imposed on the entropy numbers in a weaker metric than the uniform norm. We now formulate his result.

Let \(Y_s:= \{y_j\}_{j=1}^s \subset \Omega\) be a set of sample points from the domain \(\Omega\). Introduce a seminorm

$$\|f\|_{Y_s}:=\|f\|_{L_{ \infty }(Y_s)} := \max_{1\le j\le s} \mathopen|f(y_j)|.$$

Clearly, for any \(Y_s\) we have \(\|f\|_{Y_s} \le \|f\|_ \infty \). The following result is from [15] (see Corollary 3.4 there).

Theorem 2.3.

Let \(1\le q< \infty \). There exists a number \(C_1(q)>0\) such that for \(m\) and \(B\) satisfying

$$m\ge C_1(q) NB^q (\log N)^{w(q)},\qquad w(1):=2, \quad w(q) := \max\{q,2\}-1\quad\textit{for }\ 1<q< \infty ,$$

and for a subspace \(X_N\) satisfying for any set \(Y_m\subset \Omega\) the condition

$$ \varepsilon_k(X^q_N,L_{ \infty }(Y_m)) \le B \biggl( \frac Nk \biggr)^{\!1/q}, \qquad 1\leq k\le N,$$
(2.3)

there are points \(\xi^j\in\Omega,\) \(j=1,\dots,m,\) such that for any \(f\in X_N\) we have

$$\frac{1}{2}\|f\|_q^q \le \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^q \le \frac{3}{2}\|f\|_q^q.$$

We now proceed to the proof of Theorem 1.2.

Proof of Theorem 1.2 .

We treat separately four cases. We have

$$ X_N = {\mathcal R} {\mathcal T} (Q_n^\gamma),\qquad N=|Q_n^\gamma| \asymp 2^n n^{\nu-1}.$$
(2.4)

Case \(q=1\). \(\,\)We use Theorem 2.1 here. We obtain the required bounds on the entropy numbers from Proposition 3.1. It gives \(B=C(\gamma)n\). Therefore, by Theorem 2.1 we obtain

$$ {\mathcal R} {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,1) \qquad \text{provided}\quad m \ge C(\gamma)|Q_n^\gamma| n^3,$$
(2.5)

which is claimed in Theorem 1.2.

Case \(q\in (1,2]\). \(\,\)We use Theorem 2.3 here. We obtain the required bounds on the entropy numbers from Proposition 3.1. It gives \(B=C(q,\gamma)n^{1/q}\). Therefore, by Theorem 2.3 we obtain

$$ {\mathcal R} {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q) \qquad \text{provided}\quad m \ge C(q,\gamma)|Q_n^\gamma| n^2,$$
(2.6)

which is claimed in Theorem 1.2.

Case \(q\in (2,3)\). \(\,\)We use Theorem 2.3 here. We obtain the required bounds on the entropy numbers from Lemma 3.2. It is well known that the condition \( {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (s, \infty )\) with \(s\le C(d)\cdot 2^{nd}\) holds (see the argument in the proof of Proposition 3.1 below). It gives \(B=C(q,d)n^{1/q}MN^{-1/q}\), where \(M\) is from the Nikol’skii inequality (3.7) (see below). It is known (see [21, 22]) that

$$M\asymp 2^{n/q} n^{(\nu-1)(1-1/q)}.$$

Therefore,

$$MN^{-1/q} \asymp n^{(\nu-1)(1-2/q)}, \qquad B^q\asymp n^{(\nu-1)(q-2)+1}.$$

By Theorem 2.3 we obtain

$$ {\mathcal R} {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q) \qquad \text{provided}\quad m \ge C(q,\gamma)|Q_n^\gamma| n^{(\nu-1)(q-2) + q},$$
(2.7)

which is claimed in Theorem 1.2.

Case \(q\in [3, \infty )\). \(\,\)We use Theorem 2.2 here. In the same way as above in the case \(q\in (2,3)\), we get

$$B^q\asymp n^{(\nu-1)(q-2)+1}.$$

By Theorem 2.2 we obtain

$$ {\mathcal R} {\mathcal T} (Q_n^\gamma) \in {\mathcal M} (m,q) \qquad \text{provided}\quad m \ge C(q,\gamma)|Q_n^\gamma| n^{(\nu-1)(q-2) + 3},$$
(2.8)

which is claimed in Theorem 1.2. \(\quad\Box\)

3. Bounds of the entropy numbers

In this section we obtain bounds of the entropy numbers \(\varepsilon_k( {\mathcal R} {\mathcal T} (Q_n^\gamma)^q,L_ \infty )\) in the form (2.2). Some results on the entropy numbers \(\varepsilon_k( {\mathcal R} {\mathcal T} (Q_n)^q,L_ \infty )\) can be found in [28, Ch. 7]. However, those results are designed for proving upper bounds of the entropy numbers of classes of functions with mixed smoothness. Here we obtain bounds which serve better the sampling discretization (see a detailed discussion of such a comparison in [27, Sect. 7]). We begin with the case \(q\in [1,2]\). The following result is from [5].

Theorem 3.1.

Assume that \(X_N\) is an \(N\) -dimensional subspace of \(L_ \infty (\Omega)\) satisfying the following two conditions:

  1. (i)

    there exists a constant \(K_1>1\) such that

    $$ \|f\|_ \infty \leq (K_1N)^{1/2}\|f\|_2\qquad \forall f\in X_N;$$
    (3.1)
  2. (ii)

    there exists a constant \(K_2>1\) such that

    $$ \|f\|_ \infty \leq K_2 \|f\|_{\log N}\qquad \forall f\in X_N.$$
    (3.2)

Then for each \(1\leq q\leq 2\) there exists a constant \(C(q)>0\) depending only on \(q\) such that

$$ \varepsilon_k(X_N^q,L_ \infty ) \leq C(q) \bigl(K_1K_2^2\log N\bigr)^{1/q} \begin{cases} \displaystyle \!\biggl( \frac Nk \biggr)^{\!1/q}, & \textit{ }\, \displaystyle 1\leq k\leq N,\\\displaystyle 2^{-k/N}, & \textit{ }\, \displaystyle k>N. \end{cases}$$
(3.3)

We now apply Theorem 3.1 to the case \(X_N= {\mathcal R} {\mathcal T} (Q_n^\gamma)\). Clearly, in this case \(N=\dim {\mathcal R} {\mathcal T} (Q_n^\gamma) = |Q_n^\gamma| \asymp 2^n n^{\nu-1}\).

Proposition 3.1.

Let \(q\in [1,2]\). We have the bound

$$ \varepsilon_k\bigl( {\mathcal R} {\mathcal T} (Q_n^\gamma)^q,L_ \infty \bigr) \le C(q,\gamma) n^{1/q} \biggl( \frac{|Q_n^\gamma|}{k} \biggr)^{\!1/q}.$$
(3.4)

Proof.

It is well known and easy to check that condition (i) is satisfied with \(K_1=1\). Condition (ii) follows from known results on sampling discretization. We now explain it. Let \(\Pi_n := [-2^n,2^n]^d\) be a \(d\)-dimensional cube. It is known (see, for instance, [28, Theorem 3.3.15]) that there exists a set \(Y_s\) with \(s \le C_1(d)\cdot 2^{nd}\) such that for all \(1\le p\le \infty \) and \(f\in {\mathcal R} {\mathcal T} (\Pi_n)\)

$$ C_2(d)\|f\|_p \le \|f_{Y_s}\|_{\ell_{p,s}} \le C_3(d)\|f\|_p.$$
(3.5)

It remains to note that \(Q_n^\gamma \subset \Pi_n\) and that in \({\mathbb R}^s\) we have

$$ \| {\mathbf x} \|_{\ell_ \infty } \le C(a) \| {\mathbf x} \|_{\ell_{a\log s,s}}.\ \quad\Box$$
(3.6)

We now proceed to the case \(q\in (2, \infty )\). We will use the following result from [15], which was proved with the help of deep results from functional analysis (see [20, Lemma 16.5.4]).

Lemma 3.1.

Let \(q\in (2, \infty )\). Assume that for any \(f\in X_N\) we have

$$ \|f\|_ \infty \le M\|f\|_q$$
(3.7)

with some constant \(M\). Then for \(k\in [1,N]\) we have for any \(Y_s\)

$$ \varepsilon_k(X_N^q,L_ \infty (Y_s)) \le C(q)(\log s)^{1/q} MN^{-1/q}\biggl( \frac Nk \biggr)^{\!1/q}.$$
(3.8)

We would like to estimate the entropy numbers in the uniform norm. For that purpose we derive from Lemma 3.1 the following statement.

Lemma 3.2.

Let \(q\in (2, \infty )\). Assume that for any \(f\in X_N\) we have (3.7) with some constant \(M\). Assume also that \(X_N \in {\mathcal M} (s, \infty )\) with \(s\le aN^c\). Then for \(k\in [1,N]\) we have

$$ \varepsilon_k(X_N^q,L_ \infty ) \le C(q,a,c)(\log N)^{1/q} MN^{-1/q}\biggl( \frac Nk \biggr)^{\!1/q}.$$
(3.9)

Proof.

The condition \(X_N \in {\mathcal M} (s, \infty )\) means that there exists a set \(Y_s\) such that for any \(f\in X_N\) we have

$$ \|f\|_ \infty \le C_1\|f\|_{Y_s}.$$
(3.10)

Lemma 3.1, relation (3.10), and inequality \(\log s \le c\log N\) imply Lemma 3.2. \(\quad\Box\)

We now show how to derive a bound on the entropy numbers \(\varepsilon_k(X_N^q,L_ \infty (Y_s))\), obtained in [15], from Theorem 3.1.

Proposition 3.2.

Assume that \(X_N\) is an \(N\)-dimensional subspace of \(L_ \infty (\Omega)\) satisfying condition (i) of Theorem 3.1. Then for each \(1\leq q\leq 2\) and any \(Y_s\) with \(\log s \le a \log N\) there exists a constant \(C(q,a)>0\) depending only on \(q\) and \(a\) such that

$$ \varepsilon_k(X_N^q,L_ \infty (Y_s)) \leq C(q,a) (K_1\log N)^{1/q} \begin{cases} \displaystyle \!\biggl( \frac Nk \biggr)^{\!1/q}, & \textit{ }\, \displaystyle 1\leq k\leq N,\\\displaystyle 2^{-k/N}, & \textit{ }\, \displaystyle k>N. \end{cases}$$
(3.11)

Proof.

Using [5, Lemma 4.3] we discretize simultaneously the \(L_q\) and \(L_2\) norms, i.e., replace \(\Omega\) by \(\Omega_N\) with \(8K_1N^{a+2}\le |\Omega_N| \le CK_1N^{a+2}\) to get for \(p=q\) and \(p=2\)

$$\frac{1}{2} \|f\|_p \le \|f\|_{L_p(\Omega_N)} \le \frac{3}{2} \|f\|_p,\qquad \|f\|_{L_p(\Omega_N)}^p := \frac{1}{N}\sum_{\omega \in\Omega_N} \mathopen|f(\omega)|^p.$$

Note that the Nikol’skii inequality (3.1) implies the inequality

$$ \|f\|_ \infty \leq (K_1N)^{1/q}\|f\|_q \qquad \forall f\in X_N.$$
(3.12)

For a given \(Y_s\) consider a new domain \(\Omega_S := \Omega_N \cup Y_s\), \(|\Omega_S|=S\). Then

$$\frac{1}{S} \sum_{j=1}^s |f(y_j)|^q \le \frac{1}{S} \kern1pt s K_1N \|f\|_q^q \le (8N)^{-1} \|f\|_q^q.$$

This implies that \(\|f\|_{L_q(\Omega)} \asymp \|f\|_{L_q(\Omega_S)}\). In the same way we obtain \(\|f\|_{L_2(\Omega)} \asymp \|f\|_{L_2(\Omega_S)}\). We now want to apply Theorem 3.1 to \(X_N\) restricted to \(\Omega_S\). Condition (i) is satisfied because of \(\|f\|_{L_2(\Omega)} \asymp \|f\|_{L_2(\Omega_S)}\). Relation (3.6) guarantees that condition (ii) of Theorem 3.1 is satisfied in the case of \(\Omega_S\). Therefore, applying Theorem 3.1 to \(X_N\) restricted to \(\Omega_S\), we obtain the bounds of the entropy numbers in the metric \(L_ \infty (\Omega_S)\). Obviously, \(\| \kern1pt {\cdot} \kern1pt \|_{L_ \infty (Y_s)} \le \| \kern1pt {\cdot} \kern1pt \|_{L_ \infty (\Omega_S)}\). \(\quad\Box\)

A comment on limitations.

In Proposition 3.1, which is a corollary of Theorem 3.1, we proved the following bound for \(X_N = {\mathcal R} {\mathcal T} (Q_n^\gamma)\) and \(1\le q\le 2\):

$$ \varepsilon_k(X^q_N,L_ \infty ) \le C(q,\gamma)(\log N)^{1/q} \biggl( \frac Nk \biggr)^{\!1/q}, \qquad 1\le k \le N.$$
(3.13)

Open problem 2.

Could we replace \((\log N)^{1/q}\) by \((\log N)^{\alpha}\) with \(\alpha<1/q\) in the bound (3.3) of Theorem 3.1?

It follows from known results on the behavior of the entropy numbers of the classes \( {\mathbf W} ^{a,b}_q\) of functions with mixed smoothness that for \(1\le q< \infty \) it must be \(\alpha \ge 1/2\). We now give a definition of these classes.

Define for \(f\in L_1\)

$$\delta_ {\mathbf s} (f) := \sum_{ {\mathbf k} \in\rho( {\mathbf s} )} \widehat{f}{} ( {\mathbf k} ) e^{i( {\mathbf k} , {\mathbf x} )}, \qquad \widehat{f}{} ( {\mathbf k} ):= (2\pi)^{-d}\intop_{[0,2\pi]^d}\! f( {\mathbf x} )e^{-i( {\mathbf k} , {\mathbf x} )}\,d {\mathbf x} ,$$

and

$$f_l:=\sum_{\| {\mathbf s} \|_1=l}\delta_ {\mathbf s} (f), \qquad l\in{\mathbb N}\cup\{0\}.$$

Consider the class (see [24])

$${\mathbf W} ^{a,b}_q:=\bigl\{f \colon\, \,\|f_l\|_q \le 2^{-al} \kern1pt \overline l{ \kern1pt }^{(d-1)b}\bigr\},\qquad \overline l:=\max\{l,1\}.$$

Let \(X_N := {\mathcal T} (Q_n)\) in dimension \(d=2\). Then \(N\asymp 2^nn\). If (3.13) holds for all \(n\in{\mathbb N}\), then by [28, Theorem 7.7.15] we obtain for \(a>1/q\)

$$ \varepsilon_k( {\mathbf W} ^{a,b}_q,L_ \infty ) \le C(q,a,b) k^{-a} (\log k)^{a+b +\alpha}.$$
(3.14)

On the other hand, by [28, Theorem 7.7.10], for \(q=1\) and \(a>1\) we obtain

$$ \varepsilon_k( {\mathbf W} ^{a,b}_1,L_ \infty ) \asymp k^{-a} (\log k)^{a+b +1/2}.$$
(3.15)

Also, by [28, Theorem 7.7.14], for \(1<q< \infty \) and \(a>\max\{1/q,1/2\}\) we have

$$ \varepsilon_k( {\mathbf W} ^{a,b}_q,L_ \infty ) \asymp k^{-a} (\log k)^{a+b +1/2}.$$
(3.16)

Comparing (3.14) with (3.15) and (3.16), we obtain the above claim.

4. Discussion

As we pointed out in the Introduction, our main interest in this paper is sampling discretization of the \(L_q\) norms, \(1\le q< \infty \), of hyperbolic cross polynomials from \( {\mathcal T} (Q_n^\gamma)\). Theorem 1.2 provides such results. In this section we discuss the following question: Is it possible to extend Theorem 1.2 to \( {\mathcal T} (Q)\) with arbitrary \(Q\in{\mathbb Z}^d\)? This discussion will illustrate advantages and limitations of the techniques used in the proof of Theorem 1.2. Theorem 1.1 gives the sampling discretization result for all \( {\mathcal T} (Q)\) in the case \(q=2\). It turns out that in the case \(q\in [1,2)\) Theorem 1.2 can be extended to the case of arbitrary \(Q\).

Theorem 4.1.

For \(q\in [1,2)\) there are three positive constants \(C_i=C_i(q),\) \(i=1,2,3,\) such that for any \(Q\in{\mathbb Z}^d\) we have

$${\mathcal T} (Q) \in {\mathcal M} (m,q,C_2,C_3)\qquad \textit{provided}\quad m\ge C_1|Q|(\log(2|Q|))^{w(q)},$$

where

$$w(1) = 3 \qquad\textit{and}\qquad w(q) = 2 \quad\textit{for }\ q\in (1,2).$$

Proof.

Let \(X_N= {\mathcal R} {\mathcal T} (Q)\), \(N=|Q|\). First, we use Proposition 3.2. The hypotheses of that proposition (condition (3.1)) are satisfied with \(K_1=1\). Therefore, Proposition 3.2 guarantees that for each \(1\leq q\leq 2\) and any \(Y_s\) with \(\log s \le a \log N\) there exists a constant \(C(q,a)>0\) depending only on \(q\) and \(a\) such that

$$ \varepsilon_k(X_N^q,L_ \infty (Y_s)) \leq C(q,a) (\log N)^{1/q} \biggl( \frac Nk \biggr)^{\!1/q},\qquad 1\leq k\leq N.$$
(4.1)

We now apply Theorem 2.3. Set \(m=s\). The parameter \(a\) satisfying \(\log m \le a\log N\) will be chosen later. Then by (4.1) we find \(B=C(q,a) (\log N)^{1/q}\). We need to satisfy the following inequality in order to apply Theorem 2.3:

$$ m\ge C_1(q)N (C(q,a))^q (\log N)^{1+w(q)}.$$
(4.2)

Clearly, for any fixed \(a>1\) we can achieve simultaneously (4.2) and \(\log m \le a\log N\) provided \(N\ge C'(q,a)\). Thus, we apply Theorem 2.3 and complete the proof of Theorem 4.1. \(\quad\Box\)

We note that a version of Theorem 4.1 with \(w(q)=3\), \(q\in [1,2]\), follows from a theorem obtained in [5]. That theorem is formulated as follows.

Theorem 4.2.

Let \(X_N\) be an \(N\) -dimensional subspace of \(L_ \infty (\Omega)\) satisfying the following condition:

$$\|f\|_ \infty \le (K_1N)^{1/2}\|f\|_2 \qquad \forall f\in X_N,\quad \log K_1 \le \alpha \log N.$$

Then for \(q\in [1,2]\) we have

$$X_N \in {\mathcal M} (m,q)\qquad \textit{provided}\quad m\ge C(q,\alpha)N(\log N)^3.$$

We note that the key fact which allowed us to prove Theorem 4.1 is that both in Theorem 4.2 and in Proposition 3.2 we only need the Nikol’skii type inequality (3.1) between \(\| \kern1pt {\cdot} \kern1pt \|_ \infty \) and \(\| \kern1pt {\cdot} \kern1pt \|_2\). This inequality is the same for all \( {\mathcal T} (Q)\) with \(|Q|=N\). We do not know if Theorem 1.2 can be extended to \( {\mathcal T} (Q)\) with arbitrary \(Q\in{\mathbb Z}^d\) in the case \(q\in (2, \infty )\). Our proof of Theorem 1.2 in the case \(q\in (2, \infty )\) is based on the Nikol’skii type inequality (3.7) between \(\| \kern1pt {\cdot} \kern1pt \|_ \infty \) and \(\| \kern1pt {\cdot} \kern1pt \|_q\), which depends on \(Q\) rather than only on \(|Q|\).

Open problem 3.

Is it true that for \(q\in (2, \infty )\) and \(d\in{\mathbb N}\) there are positive constants \(C_i=C_i(q,d)\), \(i=1,2,3\), and \(c(q,d)\) such that for any \(Q\in{\mathbb Z}^d\) we have

$${\mathcal T} (Q) \in {\mathcal M} (m,q,C_2,C_3) \qquad \text{provided} \quad m\ge C_1|Q| (\log(2|Q|))^{c(q,d)}?$$

We also refer the reader to a list of open problems on sampling discretization in [6].

The cornerstone of the above-discussed technique of proving sampling discretization results is the entropy bounds of the type

$$ \varepsilon_k(X^q_N,L_ \infty ) \le B \biggl( \frac Nk \biggr)^{\!1/q}, \qquad 1\leq k\le N,\quad 1\le q< \infty .$$
(4.3)

Thus, the problem of finding conditions on \(X_N\) which guarantee relation (4.3) is a natural problem. It is well known (see, for instance, [4]) that relation (4.3) for \(k=1\) implies the following Nikol’skii type inequality for \(X_N\):

$$ \|f\|_ \infty \le 4BN^{1/q}\|f\|_q\qquad \forall f\in X_N.$$
(4.4)

Therefore, the Nikol’skii type inequality (4.4) is a necessary condition for (4.3) to hold. Lemma 3.2 shows that in the case \(q\in (2, \infty )\) condition (4.4), combined with one more condition \(X_N\in {\mathcal M} (s, \infty )\), \(s\le aN^c\), implies a slightly weaker inequality than in (4.3); namely, instead of \(B\) we get \(B'= BC(q,a,c)(\log N)^{1/q}\).