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.     

Quantum integration in Sobolev classes

We study high-dimensional integration in the quantum model of computation. We develop quantum algorithms for integration of functions from Sobolev classes W_p^r([0,1]^d) and analyze their convergence rates. We also prove lower bounds which show that the proposed algorithms are, in many cases, optimal within the setting of quantum computing. This extends recent results of Novak on integration of functions from Hölder classes.     

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.     

On the restriction map of the Fourier-Stieltjes algebra B(G) and Bp(G)

G is a locally compact group that contains the semidirect product J of a closed normal subgroup H and a closed connected subgroup K. Conditions on J are given that imply that the restriction map B_p(G) → B_p(H) (1 < p < ∞; G amenable if p ≠ 2) of the Fourier-Stieltjes algebras is not surjective. It is also shown that if the restriction map B(J) → B(H) is surjective, J need not be a direct product, even if H is nilpotent.     

On countable bounded tightness for spaces Cp(X)

It is well known that the space C_p([0,1]) has countable tightness but it is not Fréchet-Urysohn. Let X be a Cech-complete topological space. We prove that the space C_p(X) of continuous real-valued functions on X endowed with the pointwise topology is Fréchet-Urysohn if and only if C_p(X) has countable bounded tightness, i.e., for every subset A of C_p(X) and every x in the closure of A in C_p(X) there exists a countable and bounding subset of A whose closure contains x. We study also the problem when the weak topology of a locally convex space has countable bounded tightness. Additional results in this direction are provided.     

Quantum complexity of parametric integration

We study parametric integration of functions from the class C^r([0,1]^d₁+d₂) to C([0,1]^d₁) in the quantum model of computation. We analyze the convergence rate of parametric integration in this model and show that it is always faster than the optimal deterministic rate and in some cases faster than the rate of optimal randomized classical algorithms.     

Isomorphisms between Lp-function spaces when p < 1

We prove a number of results concerning isomorphisms between spaces of the type L_p(X), where X is a separable p-Banach space and 0 < p < 1. Our results imply that the quotient of L_p([0, 1] × [0, 1]) by the subspace of functions depending only on the first variable is not isomorphic to L_p, answering a question of N. T. Peck. More generally if $\text{B}$₀ is a sub-σ-algebra of the Borel sets of [0, 1], then $\text{L}{}_{\mathrm{p}}\text{([0, 1])}\text{L}{}_{\mathrm{p}}\text{([0, 1]}$, $\text{B}$₀) is isomorphic to L_p if and only if L_p([0, 1], B₀) is complemented. We also show that L_p has, up to isomorphism, at most one complemented subspace non-isomorphic to L_p and classify completely those spaces X for which $\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}$. In particular if $\text{L(L}{}_{\mathrm{p}}\text{, X) = {0}}\text{and}\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}$ then $\text{X ? l}{}_{\mathrm{p}}$ or is finite-dimensional. If X has trivial dual and $\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}\text{then}\text{X ? L}{}_{\mathrm{p}}$.     

Weak solution of (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0))u′(0) = ku(0), r(L, u(L))u′ (L) = hu(L) and k, h are suitable elements of [0, ∞]

We consider weak solutions to the nonlinear boundary value problem (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0)) u′(0) = ku(0), r(L, u(L)) u′(L) = hu(L) and k, h are suitable elements of [0, ∞]. In addition to studying some new boundary conditions, we also relax the constraints on r(x, u) and (Fu)(x). r(x, u) > 0 may have a countable set of jump discontinuities in u and r(x, u)^?1?L_q((0, L) × (0, p)). F is an operator from a suitable set of functions to a subset of L_p(0, L) which have nonnegative values. F includes, among others, examples of the form (Fu)(x) = (1 ? H(x ? x₀)) u(x₀), (Fu)(x) = ∫_x^Lf(y, u(y)) dy where f(y, u) may have a countable set of jump discontinuities in u or F may be chosen so that (Fu)′(x) = ? g(x, u(x)) u′(x) ? q(x) u(x) ? f(x, u(x)) where q is a distributional derivative of an L₂(0, L) function.     

On property Br

We improve the lower and upper bounds reported by Herzog and Schönheim for m_r(p), the minimum number m such that there exists a family $\text{F}$ of m sets, each containing p elements, and $\text{F}$ not having property B_r.     

The Br property and chromatic numbers of generalized graphs

The concept of property B_r is introduced, generalizing property B due to E. Miller. Bounds are established for the minimum number m_r(p), such that there exists a family F of m_r(p) sets, each consisting of p elements and F not having the property B_r.     

The Cauchy problem for nonhomogeneous Navier-Stokes equations inL q([0,T);L p)

In this paper the Cauchy problem for a class of nonhomogeneous Navier-Stokes equations in the infinite cylinderS _T =ℝⁿ x [0,T) is considered. We construct a unique local solution inL ^q([0,T);L ^p (ℝ ⁿ )) for a class of nonhomogeneous Navier-Stokes equations provided that initial data are inL ^r (ℝ ⁿ ), wherer>1 is an exponent determined by the structure of nonlinear terms andp,q are such that 2/q=n(1/r−1/p). Meanwhile under suitable conditions we also obtain thatu(t)≠L ^q([0,∞];L ^p (ℝ ⁿ )) provided that initial data are sufficiently small. This work is supported by the National Natural Sciences Foundation of China and the Foundation of LNM Laboratory of Institute of Mechanics of the Chinese Academy of Sciences.     

Smoothness and duality in Lp(E, μ)

Let (T, Σ, μ) be a measure space, E a Banach space, and L_p(E, μ) the Lebesque-Bochner function spaces for 1 < p < ∞. It is shown that L_p(E, μ) is smooth if and only if E is smooth. From this result a Radon-Nikodym theorem for conjugates of smooth Banach spaces is established, and thus a general geometric condition on E sufficient to ensure that $\text{L}{}_{\mathrm{p}}\text{(E, μ)}{}^1\text{? L}{}_{\mathrm{q}}\text{(E}{}^1\text{, μ)}$ for all p, 1 < p < ∞. Alternate proofs of certain known results concerning the duals of L_p(E, μ) spaces are provided.     

On some special codes over Fp + uFp + uFp

We define a new map between codes over F_p + uF_p + u²F_p and F_p which is different to that defined in [2]. It is proved that the image of the linear cyclic code over the commutative ring F_p + uF_p + u²F_p with length n under this map is a distance-invariant quasi-cyclic code of index p² with length p²n over F_p. Moreover, it is proved that, if (n, p) = 1, then every code with length p²n over F_p which is the image of a linear (1 − u²)-cyclic code with length n over F_p + uF_p + u²F_p under this map is permutation equivalent to a quasi-cyclic code of index p².     

On the space Ext for the group SL(2, q)

We consider the space Ext ^r (A,B) = Ext _KG ^r (A, B), where G = SL(2, q), q = p ⁿ , K is an algebraically closed field of characteristic p, A and B are irreducible KG-modules, and r ? 1. Carlson [6] described a basis of Ext ^r (A, B) in arithmetical terms. However, there are certain difficulties concerning the dimension of such a space. In the present article, we find the dimension of Ext ^r (A, B) for r = 1, 2 (in the above-mentioned article, Carlson presents the corresponding assertions without proofs; moreover, there are errors in their formulations). As a corollary, we find the dimension of the space H ^r (G, A), where A is an irreducible KG-module. This result can be used in studying nonsplit extensions of L ₂(q).     

Multiplicativity of lp norms for matrices. II

For 1 ? p ? ∞, let

$\text{|A|}{}_{\mathrm{p}}\text{=}\text{Σ}\text{i=1}\text{m}\text{Σ}\text{j=1}\text{n}\text{, |α}{}_{\mathrm{ij}}\text{|}{}^{\mathrm{p}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}$

, be the l_p norm of an m × n complex A = (α_ij) ?C_{m × n}. The main purpose of this paper is to find, for any p, q ? 1, the best (smallest) possible constants τ(m, k, n, p, q) and σ(m, k, n, p, q) for which inequalities of the form

$\text{|AB|}{}_{\mathrm{p}}\text{? τ(m, k, n, p, q) |A|}{}_{\mathrm{p}}\text{|B|}{}_{\mathrm{q}}\text{, |AB|}{}_{\mathrm{p}}\text{? σ (m, k, n, p, q)|A|}{}_{\mathrm{q}}\text{|B|}{}_{\mathrm{p}}$

hold for all A?C_{m × k}, B?C_{k × n}. This leads to upper bounds for inner products on C^k and for ordinary l_p operator norms on C_{m × n}.     

Best approximation by ridge functions in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-spaces

We study the approximation of the classes of functions by the manifold R _n formed by all possible linear combinations of n ridge functions of the form r(a · x)): It is proved that, for any 1 ≤ q ≤ p ≤ ∞, the deviation of the Sobolev class W ^r _p from the set R _n of ridge functions in the space L _q (B ^d ) satisfies the sharp order n ^-r/(d-1).     

Average Width and Optimal Interpolation of the Sobolev-Wiener Class Wpq(R) in the Metric Lq(R)

In this paper, we determine the exact value of average n − K width _n(W^r_pq(R), L_q(R)) of Sobolev-Wiener class W^r_pq(R) in the metric L_q(R) for 1 > q ≥ p > ∞ and get the value of _n(W^r_p(R), L_qp(R)) for the dual case. We also solve the optimal interpolation problems of W^r_pq(R) in the metric L_q(R) and W^r_p(R) in the metric L_qp(R) for 1 < q ≤ p < ∞.     

On a continuous analogue of the stochastic difference equation Xn=ρXn-1+Bn

Let B₁, B₂, ... be a sequence of independent, identically distributed random variables, letX₀ be a random variable that is independent ofB_n forn?1, let ρ be a constant such that 0<ρ<1 and letX₁,X₂, ... be another sequence of random variables that are defined recursively by the relationshipsX_n=ρX_n-1+B_n. It can be shown that the sequence of random variablesX₁,X₂, ... converges in law to a random variableX if and only ifE[log⁺¦B₁¦]<∞. In this paper we let {B(t):0≦t<∞} be a stochastic process with independent, homogeneous increments and define another stochastic process {X(t):0?t<∞} that stands in the same relationship to the stochastic process {B(t):0?t<∞} as the sequence of random variablesX₁,X₂,...stands toB₁,B₂,.... It is shown thatX(t) converges in law to a random variableX ast →+∞ if and only ifE[log⁺¦B(1)¦]<∞ in which caseX has a distribution function of class L. Several other related results are obtained. The main analytical tool used to obtain these results is a theorem of Lukacs concerning characteristic functions of certain stochastic integrals.     

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.     

A remark about the interpolation of spaces of continuous, vector-valued functions

If A is a sectorial operator on a Banach space X, then the space C([0,1];(X,D(A))_θ,∞) is a subspace of the interpolation space (C([0,1];X),C([0,1];D(A)))_θ,∞. The inclusion is strict in general.