Optimal Order of Convergence and (In)Tractability of Multivariate Approximation of Smooth Functions

We study the approximation problem for C ^∞ functions f:[0,1] ^d →? with respect to a W _p ^m -norm. Here, m=[m,m,…,m], d times, with the norm of the target space defined in terms of up to m partial derivatives with respect to all d variables. The optimal order of convergence is infinite, hence excellent, but the problem is still intractable and suffers from the curse of dimensionality if m≥1. This means that the order of convergence supplies incomplete information concerning the computational difficulty of a problem. For m=0 and p=2, we prove that the problem is not polynomially tractable, but that it is weakly tractable.     

Limits of translates of divergent geodesics and integral points on one-sheeted hyperboloids

For any non-uniform lattice Γ in SL₂(?), we describe the limit distribution of orthogonal translates of a divergent geodesic in Γ\SL₂(?). As an application, for a quadratic form Q of signature (2, 1), a lattice Γ in its isometry group, and v ₀ ∈ ?³ with Q(v ₀) > 0, we compute the asymptotic (with a logarithmic error term) of the number of points in a discrete orbit v ₀Γ of norm at most T, when the stabilizer of v ₀ in Γ is finite. Our result in particular implies that for any non-zero integer d, the smoothed count for the number of integral binary quadratic forms with discriminant d ² and with coefficients bounded by T is asymptotic to c · T log T + O(T).     

Metric entropy of the integration operator and small ball probabilities for the Brownian sheet

Let T_d : L₂([0, 1]^d) → C([0, 1]^d) be the d-dimensional integration operator. We show that its Kolmogorov and entropy numbers decrease with order at least k⁻¹ (log k)d− 1/2. From this we derive that the small ball probabilities of the Brownian sheet on [0, 1]^d under the C([0, 1]^d)-norm can be estimated from below by exp(−Cɛ⁻²¦ log ɛ¦^2d−1), which improves the best known lower bounds considerably. We also get similar results with respect to certain Orlicz norms.     

On the characteristic connection of gwistor space

We give a brief presentation of gwistor spaces, which is a new concept from G ₂ geometry. Then we compute the characteristic torsion T ^c of the gwistor space of an oriented Riemannian 4-manifold with constant sectional curvature k and deduce the condition under which T ^c is ?^c-parallel; this allows for the classification of the G ₂ structure with torsion and the characteristic holonomy according to known references. The case of an Einstein base manifold is envisaged.     

Real quadrics in C n , complex manifolds and convex polytopes

In this paper, we investigate the topology of a class of non-Kähler compact complex manifolds generalizing that of Hopf and Calabi-Eckmann manifolds. These manifolds are diffeomorphic to special systems of real quadrics C ⁿ which are invariant with respect to the natural action of the real torus (S ¹) ⁿ onto C ⁿ . The quotient space is a simple convex polytope. The problem reduces thus to the study of the topology of certain real algebraic sets and can be handled using combinatorial results on convex polytopes. We prove that the homology groups of these compact complex manifolds can have arbitrary amount of torsion so that their topology is extremely rich. We also resolve an associated wall-crossing problem by introducing holomorphic equivariant elementary surgeries related to some transformations of the simple convex polytope. Finally, as a nice consequence, we obtain that affine non-Kähler compact complex manifolds can have arbitrary amount of torsion in their homology groups, contrasting with the Kähler situation.     

G‐invariant persistent homology

Classical persistent homology is a powerful mathematical tool for shape comparison. Unfortunately, it is not tailored to study the action of transformation groups that are different from the group Homeo(X) of all self‐homeomorphisms of a topological space X. This fact restricts its use in applications. In order to obtain better lower bounds for the natural pseudo‐distance d_G associated with a group G ? Homeo(X), we need to adapt persistent homology and consider G‐invariant persistent homology. Roughly speaking, the main idea consists in defining persistent homology by means of a set of chains that is invariant under the action of G. In this paper, we formalize this idea and prove the stability of the persistent Betti number functions in G‐invariant persistent homology with respect to the natural pseudo‐distance d_G. We also show how G‐invariant persistent homology could be used in applications concerning shape comparison, when the invariance group is a proper subgroup of the group of all self‐homeomorphisms of a topological space. In this paper, we will assume that the space X is triangulable, in order to guarantee that the persistent Betti number functions are finite without using any tameness assumption. Copyright © 2014 John Wiley & Sons, Ltd.     

Natural Pseudo-Distance and Optimal Matching between Reduced Size Functions

This paper studies the properties of a new lower bound for the natural pseudo-distance. The natural pseudo-distance is a dissimilarity measure between shapes, where a shape is viewed as a topological space endowed with a real-valued continuous function. Measuring dissimilarity amounts to minimizing the change in the functions due to the application of homeomorphisms between topological spaces, with respect to the L _∞-norm. In order to obtain the lower bound, a suitable metric between size functions, called matching distance, is introduced. It compares size functions by solving an optimal matching problem between countable point sets. The matching distance is shown to be resistant to perturbations, implying that it is always smaller than the natural pseudo-distance. We also prove that the lower bound so obtained is sharp and cannot be improved by any other distance between size functions.     

Schauder estimates for a class of second order elliptic operators on a cube

We consider a class of second order elliptic operators on a d-dimensional cube S_d. We prove that if the coefficients are of class C^k+δ(S_d), with k=0,1 and δ∈(0,1), then the corresponding elliptic problem admits a unique solution u belonging to C^k+2+δ(S_d) and satisfying non-standard boundary conditions involving only second order derivatives.     

The convergence of Cesaro averages for certain nonstationary Markov chains

If P is a stochastic matrix corresponding to a stationary, irreducible, positive persistent Markov chain of period d>1, the powers Pⁿ will not converge as n → ∞. However, the subsequences P^nd+k for k=0,1,...d-1, and hence Cesaro averages Σⁿ_k-1 P^k/n, will converge. In this paper we determine classes of nonstationary Markov chains for which the analogous subsequences and/or Cesaro averages converge and consider the rates of convergence. The results obtained are then applied to the analysis of expected average cost.     

Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity

If S?{0,1};^* and S′ = {0,1}^*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A_n→A′_n with unique interpolants I_n that define S∩{0,1}ⁿ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T^p for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Homogenization of the parabolic cauchy problem in the Sobolev class H<Superscript>1</Superscript>(R<Superscript>d</Superscript>)

Homogenization in the small period limit for the solution ue of the Cauchy problem for a parabolic equation in R^d is studied. The coefficients are assumed to be periodic in R^d with respect to the lattice ɛG. As ɛ → 0, the solution u ɛ converges in L2(R^d) to the solution u0 of the effective problem with constant coefficients. The solution u ɛis approximated in the norm of the Sobolev space H ¹(R^d) with error O( ɛ); this approximation is uniform with respect to the L2-norm of the initial data and contains a corrector term of order ɛ. The dependence of the constant in the error estimate on time t is given. Also, an approximation in H ¹(R^d) for the solution of the Cauchy problem for a nonhomogeneous parabolic equation is obtained.     

具有奇异性的周期椭圆算子的绝对连续性

该文研究周期椭圆算子sun from(j,l=1) to d D_(jw)(x)a_(jl)D_l+V(x)在R~d(d≥3)中的谱性质,其中A=(a_(jl))是d×d阶的实常值正定矩阵,V(x)和w(x)是关于相同格点的周期标量函数,并且w(x)是正的.利用文中第一作者建立的d-环面上的一致Sobolev不等式,证明了该算子的谱是纯绝对连续的,如果V∈L_(loc)~(2pd/(d+2p))(R~d)且w∈A_(1+α)~(p,∞)(T~d)∩L~∞(T~d)(α0,p≥d),或者V∈L_(loc)~(2d/3)/(R~d),ω∈C~1(T~d),或者V∈L_(loc)~(d/2)(R~d),w∈L_(2,loc)~(d/2)(T~d).     

Superlocalization of waves and electrons and hopping conductivity on classical and superconductive fractals

We have found an unexpected paradoxical situation in the percolation transition: the superconductive behavior below and above the threshold. We have found also the two different density of states d_s=4/3 and d_v=1.05 and the inverse localization lengths for fractons with the scalar and vector interactions, respectively. In this concept the wave functions of electrons or waves on an incipient percolation cluster and fractal dilute structure exhibit superlocalization behavior of the form ψ(r)∝exp[−r^d_φ] with values of d_φ1=1.73 and d_φ2=2.4 for the former and the latter. Applications of these results for thermally activated hopping conductivity σ(t)∝exp[−(T₀/T)^β] between impurities on a random fractal structure give the values of β=2/5 for the scalar and β=1/2 (Mott's law) for the vector interactions, respectively. Band states are localized in classical and superlocalized in superconductive percolations.     

A moment theorem for completely hyperexpansive operators

Given a family $ \{ A_m^x \} _{\mathop {m \in \mathbb{Z}_ + ^d }\limits_{x \in X} } $ (X is a non-empty set) of bounded linear operators between the complex inner product space $ \mathcal{D} $ and the complex Hilbert space ? we characterize the existence of completely hyperexpansive d-tuples T = (T ₁, … , T _d ) on ? such that A _m ^x = T ^m A ₀ ^x for all m ? ? ₊ ^d and x ? X.     

On a characterization of Dilworth truncations of combinatorial geometries

A combinatorial geometry being given, a Dilworth structure is defined to be a family of point subsets for which properties (1_d), (2_d), (3_d) in sect.2 hold. Let T^d(G) denote Dilworth truncation of a geometry G. It is possible to associa te with T^d(G) a Dilworth structure D(G) (see sect.2). It will be proved that a one-to-one and onto corresponden ce exists between Dilworth structures S of a connected geo metry K and those geometries G such that T^d(G)=K and D(G)=S.     

Fixed points and iterations of mean-type mappings

Let (X, d) be a metric space and T: X → X a continuous map. If the sequence (T ⁿ ) _n∈? of iterates of T is pointwise convergent in X, then for any x ∈ X, the limit $$\mu _T (x) = \mathop {\lim }\limits_{n \to \infty } T^n (x)$$ is a fixed point of T. The problem of determining the form of µ _T leads to the invariance equation µ _T ○ T = µ _T , which is difficult to solve in general if the set of fixed points of T is not a singleton. We consider this problem assuming that X = I ^p , where I is a real interval, p ≥ 2 a fixed positive integer and T is the mean-type mapping M =(M ₁,...,M _p ) of I ^p . In this paper we give the explicit forms of µ_M for some classes of mean-type mappings. In particular, the classical Pythagorean harmony proportion can be interpreted as an important invariance equality. Some applications are presented. We show that, in general, the mean-type mappings are not non-expansive.     

On the distance matrix of a tree

For a tree T on n vertices, let D(T)=(d_ij) denote the distance matrix of T, i.e., d_ij(T) is just the length of the unique path then the ith vertex and the jth vertex of T. Denote by Δ_T(x) the characteristic polynom, of D(T), so that Δ_T(x) = det(D(T) xl). In this paper, we investigate a number of properties of Δ_T(x). In particular, we find simple expressions for the first few and last few coefficients of Δ_T(x).