Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

On the L2n 1– Extension Properties

We have proved that for all compact linear operator u from R into an L_p ([0,1], ν) (0 < p < 1) extends to L ₁ ([0,1], ν), where R denotes the closed linear subspace in L ₁ ([0,1], ν) of the Rademacher functions {r_n }_{n ? N}. In this paper, we study this type of extension for E_n ? L_2n ¹ where E_n is the n–dimensional subspace which appears in Kasin's theorem such that L_2n ¹ = E_n ⊕ E ^⊥ _n and the L_2n ¹ , L_2n ² norms are universally equivalent on both E_n , E ^⊥ _n. We show that, the precedent extension fails for the pair (E_n , L_2n ¹ ) and we generalize this to any E in an L ₁(Ω, A, P) by giving some conditions on E.     

Integration and Lipschitz functions

The aim of the paper is to prove that every f ∈ L ¹([0,1]) is of the form f = , where j _n,k is the characteristic function of the interval [k- 1 / 2 ⁿ , k / 2 ⁿ ) and Σ _n=0^∞Σ _k=1²ⁿ |a _n,k | is arbitrarily close to ||f|| (Theorem 2). It is also shown that if μ is any probabilistic Borel measure on [0,1], then for any ɛ > 0 there exists a sequence (b _n,k ) _n≧0 ^k=1,...,2n of real numbers such that and for each Lipschitz function g: [0,1] → ℝ (Theorem 3).      

Fejér summability of multi-parameter bounded Ciesielski systems

We investigate the Kronecker product of bounded Ciesielski systems, which can be obtained from the spline systems of order (m,k) in the same way as the Walsh system from the Haar system. It is shown that the maximal operator of the Fejér means of the d-dimensional Ciesielski-Fourier series is bounded from the Hardy space H _p([0,1)^d ₁ × ¨ × [0,1)^d _l) to L _p([0,1)^d) if 1/2 < p < &infin; and m _j &ge; 0, |k _j| &le; m _j + 1. By an interpolation theorem, we get that the maximal operator is also of weak type (H ₁ ^#i,L ₁) (I=1,¨,l), where the Hardy space H ₁ ^#i is defined by a hybrid maximal function and H ₁ ^#i L(logL)^l-1. As a consequence, we obtain that the Fejér means of the Ciesielski-Fourier series of a function f converge to f a.e. if f H ₁ ^#i and converge in a cone if f &isin; L ₁.     

nth order Stieltjes differential boundary operators and Stieltjes differential boundary systems

This article discusses linear differential boundary systems, which include nth-order differential boundary relations as a special case, in $\text{L}$_n^p[0,1] × $\text{L}$_n^p[0,1], 1 ? p < ∞. The adjoint relation in $\text{L}$_n^q[0,1] × $\text{L}$_n^q[0,1], $\text{1}\text{p}\text{+}\text{1}\text{q}\text{= 1}$, is derived. Green's formula is also found. Self-adjoint relations are found in $\text{L}$_n²[0,1] × $\text{L}$_n²[0,1], and their connection with Coddington's extensions of symmetric operators on subspaces of $\text{L}$_n^p[0,1] × $\text{L}$_n²[0,1] is established.     

Asymptotic Behavior of Variable-Coefficient Toeplitz Determinants

For a continuous function s\sigma defined on [0,1]×\mathbbT[0,1]\times\mathbb{T}, let \ops\op\sigma stand for the (n+1)×(n+1)(n+1)\times(n+1) matrix whose (j,k)(j,k)-entries are equal to \frac1 2pò₀^2p s( \fracjn,e^iq) e^-i(j-k)q  dq,        j,k = 0,1,...,n . \displaystyle \frac{1} {2\pi}\int_0^{2\pi} \sigma \left( \frac{j}{n},e^{i\theta}\right) e^{-i(j-k)\theta} \,d\theta, \qquad j,k =0,1,\dots,n~. These matrices can be thought of as variable-coefficient Toeplitz matrices or as the discrete analogue of pseudodifferential operators. Under the assumption that the function s\sigma possesses a logarithm which is sufficiently smooth on [0,1]×\mathbbT[0,1]\times\mathbb{T}, we prove that the asymptotics of the determinants of \ops\op\sigma are given by det[\ops] ~ G[s]⁽ⁿ⁺¹⁾E[s]     \text as   n?￥ , \det \left[\op\sigma\right] \sim G[\sigma]^{(n+1)}E[\sigma] \quad \text{ as \ } n\to\infty~, where G[s]G[\sigma] and E[s]E[\sigma] are explicitly determined constants. This formula is a generalization of the Szegö Limit Theorem. In comparison with the classical theory of Toeplitz determinants some new features appear.     

Perturbation theorems for linear hyperbolic mixed problems and applications to the compressible euler equations

The main result of this paper (which is completely new, apart from our previous and less general result proved in reference [9]) states that the nonlinear system of equations (1.11) (or, equivalently, (1.10)) that describes the motion of an inviscid, compressible (barotropic) fluid in a bounded domain Ω, gives rise to a strongly well-posed problem (in the Hadamard classical sense) in spaces H^k(Ω), k ≧ 3; see Theorem 1.4 below. Roughly speaking, if (a_n, ?_n) → (a, ?) in H^k × H^k and if f_n → f in ??²(0, T;H^k), then (v_n, g_n) → (v, g) in ?? (0, T; H^k × H^k). The method followed here (see also [8]) also applies to the non-barotropic case p = p(ρ, s) (see [10]) and to other nonlinear problems. These results are based upon an improvement of the structural-stability theorem for linear hyperbolic equations. See Theorem 1.2 below. Added in proof: The reader is referred to [29], Part I, for a concise explanation of some fundamental points in the method followed here. © 1993 John Wiley & Sons, Inc.     

Nonsoluble length of finite groups with restrictions on Sylow subgroups

By 𝔛(n) we denote the variety of all groups satisfying the law [x,y]ⁿ≡1, that is, groups with commutators of order dividing n. Let p be a prime and G a finite group whose Sylow p-subgroups have normal series of length k all of whose quotients belong to 𝔛(n). We show that the non-p-soluble length λ_p(G) of G is bounded in terms of k and n only (Theorem 1.2). In the case where p is odd, a stronger result is obtained (Theorem 1.3).     

On the solutions of the translation equation in rings of formal power series

We study in this paper solutions of the translation equation in rings of formal power series K[X] where K ∈R, C (so called one-parameter groups or flows), and even, more generally, homomorphisms Ф from an abelian group (G, +) into the group Г(K) of invertible power series in K[X]. This problem can equivalently be formulated as the question of constructing homomorphisms Ф from (G, +) into the differential group Г¹∞ describing the chain rules of higher order of C∞ functions with fixed point 0. In this paper we present the general form of these homomorphisms Ф : G → Г(K) (or L¹∞),Ф = (f_n ⁿ≤1,forwhich f₁ = l, f₂ = ... = f_p+l =0,f_p+2 ≠ 0 for fixed, but arbitrary p ≤ 0 (see Theorem 5, Corollary 6 and Theorem 6). This representation uses a sequence (w _n ^p )_n≥p+2 of universal polynomials in f_p+2 and a sequence of parameters, which determines the individual one-parameter group. Instead of (w _n ^p )_n≥p+2 we may also use another sequence (L _n ^p )_n≥p+2 of universal polynomials, and we describe the connection between these forms of the solutions.     

Strong Sperner property of the subgroup lattice of an Abelianp-group

Letn andk be arbitrary positive integers,p a prime number and L_(k ⁿ)(p) the subgroup lattice of the Abelianp-group (Z/p ^k ) ⁿ . Then there is a positive integerN(n,k) such that whenp N(n,k),L _(k ^N )(p) has the strong Sperner property.     

The mixed Lp affine surface areas for functions

In this paper, we propose a definition of a general mixed L_p Affine surface area, ?n ≠ p ∈ ?, for multiple functions. Our definition is di?erent from and is “dual” to the one in [11] by Caglar and Ye. In particular, our definition makes it possible to establish an integral formula for the general mixed L_p Affine surface area of multiple functions (see Theorem 3.1 for more precise statements). Properties of the newly introduced functional are proved such as affine invariance, and related affine isoperimetric inequalities are proved.     

ON CONVERGENCE OF WAVELET PACKET EXPANSIONS

It is well known that the-Walsh-Fourier expansion of a function from the block spaceB _q([0,1]), 1B _q in certain periodized smooth periodic non-stationary wavelet packets bases based on the Haar filters. We also consider wavelet packets based on the Shannon filters and show that the expansion of L^p-functions, 1相似文献   

Optimal query error of quantum approximation on some Sobolev classes

We study the approximation of the imbedding of functions from anisotropic and general-ized Sobolev classes into Lq([0,1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr ([0,1]d)) to Lq([0,1]d) space for all 1 q,p ∞ and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.     

New Coins from Old, Smoothly

Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O’Brien (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (N<∞) equal to 1 exists if and only if f is continuous. Nacu and Peres (Ann. Appl. Probab. 15(1A):93–115, 2005) proved that f is real analytic in an open set S⊂(0,1) if and only if such a simulation scheme exists with the probability ℙ _p (N>n) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, f is in the space C ^α [0,1] if and only if a simulation scheme as above exists with ℙ _p (N>n)≤C(Δ _n (p)) ^α , where \varDelta _n(x):=max{?{x(1-x)/n},1/n}\varDelta _{n}(x):=\max\{\sqrt{x(1-x)/n},1/n\}. The key to the proof is a new result in approximation theory: Let B⁺_n\mathcal{B}^{+}_{n} be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in C ^α [0,1] if and only if f has a series representation ?_n=1^￥F_n\sum_{n=1}^{\infty}F_{n} with F_n ? B⁺_nF_{n}\in \mathcal{B}^{+}_{n} and ∑ _k>n F _k (x)≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (Math. Ann. 151:239–251, 1963), who claimed that if some j_n ? B⁺_n\varphi_{n}\in\mathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1, then f∈C ^α [0,1].     

Asymptotic Behaviour of Iterates of Volterra Operators on L p (0, 1)

Given k ∈ L¹ (0,1) satisfying certain smoothness and growth conditions at 0, we consider the Volterra convolution operator V_k defined on L^p (0,1) by

On unconditional bases in certain Banach function spaces

Let X be a Banach space, L ([0,1])XL ¹([0,1]), with an unconditional basis. By the well-known stability property in X, there exists a unconditional basis {f _n} _m=1 , where f _n in C([0,1]), nN. In this paper, we introduce the notion that X ^*has the singularity property of X ^*at a point t ₀[0,1]. It is proved that if X ^*has the singularity property at a point t ₀ [0,1], then there exists no orthonormal, fundamental system in C([0,1]) which forms an unconditional basis in X.     

On the Asymptotically Optimal Rate of Approximation of Multiplier Operators from L p into L q

The asymptotic behavior of the n -widths of multiplier operators from L _p [0,1] into L _q [0,1] is studied. General upper and lower bounds for the n -widths in terms of the multipliers are established. Moreover, it is shown that these upper and lower bounds coincide for some important concrete examples. August 3, 1994. Date revised: November 15, 1996.     

Best N Term Approximation Spaces for Tensor Product Wavelet Bases

We consider best N term approximation using anisotropic tensor product wavelet bases ("sparse grids"). We introduce a tensor product structure ⊗_q on certain quasi-Banach spaces. We prove that the approximation spaces A^α_q(L₂) and A^α_q(H¹) equal tensor products of Besov spaces B^α_q(L_q), e.g., A^α_q(L₂([0,1]^d)) = B^α_q(L_q([0,1])) ⊗_q · ⊗_q B^α_{q · ·}(L_q([0,1])). Solutions to elliptic partial differential equations on polygonal/polyhedral domains belong to these new scales of Besov spaces.     

The Fine Structure of the n-Widths of H-Spaces in Lq(−1, 1)

The n-widths of the unit ball A_p of the Hardy space H^p in L_q( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k₁ and k₂ such that [formula]≤ d_n(A_p, L_q(−1, 1)),dⁿ(A_p, L_q(−1, 1)), δ_n(A_p, L_q(−1, 1))[formula]where d_n, dⁿ, and δ_n denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.     

Some questions in the theory of inverse problems for differential operators

For the two operatorsLy=y ⁿ +σ _k=0 ⁿ⁻² p _k (x)y( ^k ) and Ry=yⁿ+σ _k=0 ⁿ⁻² p_k(x)y(^k) with a common set of boundary conditions we establish a connection between p_k(x) and P_k(x) in the case where the weight numbers coincide and a finite number of the eigenvalues do not coincide, in terms of the eigenfunctions of these operators corresponding to the noncoincident eigenvalues and the derivatives of these functions. This enables us to recover the operator L from the operator R by solving a system of nonlinear ordinary differential equations. For Sturm-Liouville operators an analogous relation is proved for the case where infinitely many eigenvalues do not coincide. Translated from Matematicheskie Zametki, Vol. 21, No. 2, pp. 151–160, February, 1977. I wish to express my thanks to my scientific adviser V. A. Sadovnich.